fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #define PB 359
  4. #define MOD 1000000007
  5. #define MAX 250000
  6. #define NUL -99
  7. #define ll long long
  8. using namespace std;
  9.  
  10. ll h1[MAX+1];
  11. ll h2[MAX+1];
  12. ll pow[MAX+1];
  13. int ans_idx = NUL;
  14.  
  15. bool check(int a_size, int b_size, int len);
  16.  
  17. int main() 
  18. {
  19. 	string s1, s2;
  20. 	int l1, l2;
  21. 	cin >> s1 >> s2;
  22. 	l1 = s1.size();
  23. 	l2 = s2.size();
  24. 	pow[0] = 1;
  25. 	for (int i = 1; i < MAX+1; ++i)
  26. 		pow[i] = (pow[i-1] * PB) % MOD;
  27. 	h1[0] = s1[0];
  28. 	for (int i = 1; i < l1; ++i)
  29. 		h1[i] = (((h1[i-1] * PB) % MOD) + s1[i]) % MOD;
  30. 	h2[0] = s2[0];
  31. 	for (int i = 1; i < l2; ++i)
  32. 		h2[i] = (((h2[i-1] * PB) % MOD) + s2[i]) % MOD;
  33. 	int low = 0, hi = l2, mid;
  34. 	while (low < hi)
  35. 	{
  36. 		mid = (low + hi) / 2;
  37. 		if (!check(l1, l2, mid))
  38. 			hi = mid-1;
  39. 		else
  40. 			low = mid+1;	
  41. 	}
  42. 	if (ans_idx != NUL)
  43. 		cout << s1.substr(ans_idx, low-1) << '\n'<< low-1;
  44. 	else
  45. 		cout << "0" << '\n';
  46. 	return 0;
  47. }
  48.  
  49. bool check(int a_size, int b_size, int len)
  50. {
  51. 	for (int i = 0; i <= b_size-len; ++i)
  52. 	{
  53. 		for (int j = 0; j <= a_size-len; ++j)
  54. 		{
  55. 			if (j == 0)
  56. 			{
  57. 				if (h2[i+len-1] == h1[len-1])
  58. 				{
  59. 					ans_idx = j;
  60. 					return true;
  61. 				}	
  62. 			}			
  63. 			else
  64. 			{
  65. 				if(h2[i+len-1] == (h1[j+len-1] - ((h1[j-1] * pow[len]) % MOD)))
  66. 				{
  67. 					ans_idx = j;
  68. 					return true;
  69. 				}	
  70. 			}		
  71. 		}
  72. 	}
  73. 	return false;
  74. }
Success #stdin #stdout 0.01s 9344KB
comments (?)
stdin
copy 
abcadlfghijkl
abcdlfabcde
stdout
copy 
abc
3
https://ideone.com/3tdMOZ
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!