fork 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 + 1) / 2;
  37. 		if (!check(l1, l2, mid))
  38. 			hi = mid-1;
  39. 		else
  40. 			low = mid;
  41. 	}
  42. 	if (ans_idx != NUL)
  43. 		cout << s1.substr(ans_idx, low) << '\n'<< low;
  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 (i == 0)
  56. 			{
  57. 				if (j == 0)
  58. 				{
  59. 					if (h2[i+len-1] == h1[len-1])
  60. 					{
  61. 						ans_idx = j;
  62. 						return true;
  63. 					}	
  64. 				}			
  65. 				else
  66. 				{
  67. 					if(h2[i+len-1] == (h1[j+len-1] - ((h1[j-1] * pow[len]) % MOD)))
  68. 					{
  69. 						ans_idx = j;
  70. 						return true;
  71. 					}		
  72. 				}
  73. 			}
  74. 			else
  75. 			{
  76. 				if (j == 0)
  77. 				{
  78. 					if (h2[i+len-1] == h1[len-1])
  79. 					{
  80. 						ans_idx = j;
  81. 						return true;
  82. 					}	
  83. 				}	
  84. 				else
  85. 				{
  86. 					if((h2[i+len-1] - ((h2[i-1] * pow[len]) % MOD)) == (h1[j+len-1] - ((h1[j-1] * pow[len]) % MOD)))
  87. 					{
  88. 						ans_idx = j;
  89. 						return true;
  90. 					}		
  91. 				}	
  92. 			}	
  93. 		}
  94. 	}
  95. 	return false;
  96. }
Success #stdin #stdout 0.01s 9296KB
comments (?)
stdin
copy 
abc
abc
stdout
copy 
abc
3
https://ideone.com/NIAIZf
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!