fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1<<20;
  6.  
  7. struct pair_hash {
  8.     long long operator()(const pair <int, int> &a) const {
  9.         return a.first*1ll*1000000000+a.second;
  10.     }
  11. };
  12.  
  13. int n,m;
  14. char a[N];
  15. unordered_map < pair <int, int> , bool, pair_hash> used;
  16. unordered_map < pair <int, int> , int, pair_hash> state;
  17.  
  18. bool check(int x, int y, int z, int w) {
  19. 	int i=x,j=z;
  20. 	while(i<=y) {
  21. 		if(a[i]!=a[j]) return false;
  22. 		++i;
  23. 		++j;
  24. 	}
  25. 	return true;
  26. }
  27.  
  28. int recurse(int l, int r) {
  29.     if(r>n) return 0;
  30.     if(used[make_pair(l,r)]) return state[make_pair(l,r)];
  31.     int ans=1,length=r-l+1;
  32.     if(check(l,r,l+length,r+length)) ans+=recurse(l+length,r+length);
  33.     used[make_pair(l,r)]=true;
  34.     state[make_pair(l,r)]=ans;
  35.     return ans;
  36. }
  37.  
  38. int main() {
  39. 	int i,cnt,l,r;
  40.  
  41. 	scanf("%d %d", &n, &m);
  42. 	scanf("%s", a+1);
  43. 	while(m--) {
  44. 		scanf("%d %d", &l, &r);
  45. 		/*cnt=1;
  46. 		for(i=r+1;i+(r-l+1)-1<=n;i+=(r-l+1)) {
  47. 			if(check(l,r,i,i+(r-l+1)-1)) ++cnt;
  48. 			else break;
  49. 		}
  50. 		printf("%d\n", cnt);*/
  51.         printf("%d\n", recurse(l,r));
  52. 	}
  53.  
  54. 	return 0;
  55. }
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7ZerOb
language:
C++14 (gcc 8.3)
created:
8 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!