fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. string s;
  6. ll const m=1e9+9;
  7. ll const p=31; 
  8. int const siz=1e5;
  9. ll hashpre[siz];
  10. ll inv_p[siz];
  11.  
  12. ll poww(ll x, ll n) {
  13.     long temp;
  14.     if (n==0)
  15.         return 1ll;
  16.     temp=poww(x,n/2);
  17.     if (n%2==0)
  18.         return ((temp%m)*(temp%m))%m;
  19.     else
  20.         return (((x*(temp%m))%m)*(temp%m))%m;
  21. }
  22.  
  23. void precomputation() { //calculates mod multiplicative inverse for all powers of p
  24.     inv_p[0]=1;
  25.     ll invp=poww(p,m-2);
  26.     for (int i=1;i<=siz;i++)
  27.         inv_p[i]= (inv_p[i-1]*invp)%m;
  28. }
  29.  
  30. void computehashpre() { //computes hash of all prefixes
  31.     ll prevp=p;
  32.     hashpre[0]=1;
  33.     for (int i=1;i<s.size();i++) {
  34.         hashpre[i]= (hashpre[i-1] + ((s[i]-'a'+1)*prevp)%m)%m;
  35.         prevp= (prevp*p)%m;
  36.     }
  37. }
  38.  
  39. ll hashh(int i,int j) {
  40. 	//hash(i,j) = (hash(0,j)-hash(0,i-1))*(multiplicative modulo inverse of p^i)
  41.     if (i!=0) {
  42.         ll res=hashpre[j]-hashpre[i-1];
  43.         if (res<0) res+=m;
  44.         else res%=m;
  45.         return (res*inv_p[i])%m;
  46.     }
  47.     else
  48.         return hashpre[j]%m;
  49. }
  50.  
  51. int main() {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(NULL);
  54.     precomputation(); //calculates mod multiplicative inverse for all powers of p
  55.     int t; cin>>t;
  56.     while (t--) {
  57.         cin>>s;
  58.         computehashpre(); //computes hash of all prefixes
  59.         int counter=0;
  60.         for (int i=1;i<s.size()-2;i=i+2) {
  61.             if (hashh(0,i/2)==hashh(i/2 +1,i) && hashh(i+1,(s.size()-1-i)/2 +i)==hashh((s.size()-1-i)/2 +i+1,s.size()-1))
  62.                 counter++;
  63.         }
  64.         cout<<counter<<endl;
  65.     }
  66.     return 0;
  67. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
3
abcd
aaaa
ababcdccdc
stdout
copy 
0
1
1
https://ideone.com/SSDjRD
language:
C++14 (gcc 8.3)
created:
3 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!