fork(2) download 
  1.  
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. const int base = 13331;
  9.  
  10. vector< pair<int, int> > prime[500001];
  11. long long hash[500001], power[500001];
  12. bool check[500001];
  13. char str[500001];
  14.  
  15. int main() {
  16. 	int n, q;
  17. 	scanf("%d%s%d", &n, str, &q);
  18. 	memset(check, false, sizeof(check));
  19. 	for (int i = 2; i <= n; i ++)
  20. 		if (! check[i])
  21. 			for (int j = i; j <= n; j += i) {
  22. 				int tmp = j, cnt = 0;
  23. 				while (tmp % i == 0) {
  24. 					cnt ++;
  25. 					tmp /= i;
  26. 				}
  27. 				prime[j].push_back(make_pair(i, cnt));
  28. 				check[j] = true;
  29. 			}
  30. 	hash[0] = 0;
  31. 	for (int i = 0; i < n; i ++)
  32. 		hash[i+1] = hash[i] * base + str[i];
  33. 	power[0] = 1;
  34. 	for (int i = 1; i < n; i ++)
  35. 		power[i] = power[i-1] * base;
  36. 	for (int i = 0; i < q; i ++) {
  37. 		int a, b;
  38. 		scanf("%d%d", &a, &b);
  39. 		a --;
  40. 		int len = b - a, res = 1;
  41. 		for (int j = 0; j < prime[len].size(); j ++) {
  42. 			int p = prime[len][j].first, cnt = prime[len][j].second, now = 1;
  43. 			for (int k = 0; k < cnt; k ++) now *= p;
  44. 			for (int k = cnt; k > 0; k --) {
  45. 				int l = len / now;
  46. 				long long t1 = hash[b-l] - hash[a] * power[b-a-l];
  47. 				long long t2 = hash[b] - hash[a+l] * power[b-a-l];
  48. 				if (t1 == t2) {
  49. 					res *= now;
  50. 					break;
  51. 				}
  52. 				now /= p;
  53. 			}
  54. 		}
  55. 		printf("%d\n", len / res);
  56. 	}
  57.  
  58. 	return 0;
  59. }
  60.  
Success #stdin #stdout 0.02s 17512KB
comments (?)
stdin 
8
aaabcabc
3
1 3
3 8
4 8
stdout 
1
3
5
https://ideone.com/ElokU
language:
C++ (gcc 8.3)
created:
14 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!