fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const ll BASE = 2017;
  8. const ll MOD = 1e9 + 7;
  9. const int SIZE = 30001;
  10.  
  11. ll prefix[SIZE], power[SIZE];
  12. string a, b;
  13.  
  14. void get_hash(string &s) {	
  15. 	prefix[0] = ll(s[0] - 'a' + 1);
  16. 	int n = int(s.size());
  17. 	for (int i = 1; i < n; i++) {
  18. 		prefix[i] = ((ll)prefix[i - 1] * BASE + ll(s[i] - 'a' + 1)) % MOD;
  19. 	}
  20. }
  21.  
  22. void calc_pow(int n) {
  23. 	power[0] = 1LL;
  24. 	for (int i = 1; i <= n; i++) {
  25. 		power[i] = ((ll)power[i - 1] * BASE) % MOD;
  26. 	}
  27. }
  28.  
  29. ll get_segment(int l, int r) {
  30. 	int len = r - l + 1;
  31. 	return ((prefix[r] - (ll)prefix[l - 1] * power[len]) % MOD + MOD) % MOD;
  32. }
  33.  
  34. bool possible(int len) {
  35. 	for (int i = 0; i < SIZE; i++) {
  36. 		prefix[i] = 0LL;
  37. 	}
  38. 	int n = int(a.size()), m = int(b.size());
  39. 	if (len > n || len > m) {
  40. 		return 0;
  41. 	}
  42. 	set<ll> q;
  43. 	get_hash(b);
  44. 	for (int l = 0; l <= n - len; l++) {
  45. 		int r = l + len - 1;
  46. 		q.insert(get_segment(l, r));		
  47. 	}
  48. 	get_hash(a);
  49. 	for (int l = 0; l <= n - len; l++) {
  50. 		int r = l + len - 1;
  51. 		if (q.count(get_segment(l, r))) {
  52. 			return 1;
  53. 		}
  54. 	}
  55. 	return 0;
  56. }
  57.  
  58. int main() {
  59. 	cin >> a >> b;
  60. 	int n = int(a.size()), m = int(b.size());
  61. 	int mx = max(n, m) + 1;
  62. 	calc_pow(mx);
  63. 	int l = 0, r = min(n, m) + 1, ans = 0;
  64. 	while(r - l > 1) {
  65. 		int mid = (r + l) >> 1;
  66. 		if (possible(mid)) {
  67. 			l = mid;
  68. 			ans = max(ans, mid);
  69. 		} else {
  70. 			r = mid;
  71. 		}
  72. 	}		
  73. 	cout << ans;
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 3944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ekjcDx
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!