fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct SA
  4. {
  5.     vector < vector < int > > P;
  6.     vector < vector < int > > dp;
  7.     vector < pair < pair < int , int > , int > > L;
  8.     vector < int >    RMAP , LG;
  9.     int N    , MAXLG   ;
  10.     bool save ;
  11.     string _S;
  12.     void ini()
  13.     {
  14.         int i , j ;
  15.         N = _S.length();
  16.         for(i=1;(1<<i-1)<=N;++i);
  17.         MAXLG = i;
  18.         P.resize(MAXLG);
  19.         RMAP.resize(N);
  20.         for(i=0;i<MAXLG;++i)P[i].resize(N);
  21.         L.resize(N);
  22.         for(i=0;i<N;++i)P[0][i] = _S[i];
  23.  
  24.         for(i=1;i<MAXLG;++i)
  25.         {
  26.             for(j=0;j<N;++j)L[j] = {{P[i-1][j]  , j +  (1<<i-1) < N ? P[i-1][j+(1<<i-1)]:-1  }, j };
  27.             sort(L.begin(),L.end());
  28.             for(j=0;j<N;++j)
  29.                 P[i][L[j].second] = j!=0 && L[j].first==L[j-1].first ? P[i][L[j-1].second] : j;
  30.         }
  31.         for(i=0;i<N;++i)RMAP[L[i].second] = i ;
  32. //        for(i=0;i<N;++i)
  33. //            cout<<_S.substr(L[i].second,_S.length()-L[i].second)<<'\n';
  34.     }
  35.     int compute_LCP(int x , int y )
  36.     {
  37.         if(x==y)return N - x;
  38.         int ret = 0 ;
  39.         for(int k = MAXLG-1;k>=0 && x<N && y<N;--k)
  40.             if(P[k][x]==P[k][y])
  41.                 x+=(1<<k) , y+=(1<<k) , ret+=(1<<k);
  42.         return ret;
  43.     }
  44.  
  45.     void compute_LCP()
  46.     {
  47.         int i , j ;
  48.         dp.resize(MAXLG);
  49.         LG.resize(N+1);
  50.         for(i=0;i<MAXLG;++i)dp[i].resize(N);
  51.         for(i=0;i<N-1;++i){
  52.             dp[0][i] = compute_LCP(L[i].second,L[i+1].second);
  53.         }
  54.  
  55.         LG[1] = 0;
  56.         LG[0] = -1e9;
  57.         for(i=2;i<=N;++i)LG[i] = LG[i/2]+1;
  58.         for(i=1;i<MAXLG;++i)
  59.             for(j=0;j<N-1;++j)
  60.                 dp[i][j] = min(dp[i-1][j] , (1<<i-1)+j<N-1?dp[i-1][(1<<i-1)+j]:0);
  61.     }
  62.  
  63.     int query(int x , int y)
  64.     {
  65.         if(!save){
  66.             cout<<"Send second parameter as 1\n\n";
  67.             assert(0);
  68.         }
  69.         int L = x , R = y;
  70.         if(R<L)
  71.             return N - this->L[L].second;
  72.         assert(L<=R);
  73.         return min(dp[LG[(R-L+1)]][L] , dp[LG[R-L+1]][R-(1<<LG[R-L+1])+1]);
  74.     }
  75.     int query_by_index(int x , int y)
  76.     {
  77.         if(x==y)return N - x;
  78.         return query(min(RMAP[x],RMAP[y]),max(RMAP[x],RMAP[y])- 1);
  79.     }
  80.     SA(string S ,bool go = 0 ): _S(S) {ini();if(go)compute_LCP();save = go;}
  81.  
  82.     bool check(int x , int len)
  83.     {
  84.         int i ;
  85.         for(i=0;i + x - 1 <N/2;++i)
  86.             if( query_by_index(i, N-i - x ) >= x)return 1;
  87.         return 0;
  88.     }
  89. };
  90. int main()
  91. {
  92.     ios::sync_with_stdio(0);cin.tie(0);
  93.     int N ,  i  , j ;
  94.     cin>>N;
  95.     string S;
  96.     cin>>S;
  97.     N = S.length();
  98.     string T = S;
  99.     reverse(T.begin(),T.end());
  100.     S += "$" + T;
  101.     SA obj1(S,1);
  102.     int L = 0 , R = (N%2==0?N:N-1)/2 , M;
  103.     while(L<R)
  104.     {
  105.         M = L + (R-L+1)/2;
  106.         if(obj1.check(M*2,N))
  107.             L = M ;
  108.         else
  109.             R = M - 1;
  110.     }
  111.     int ans = L * 2;
  112.     L = 0 ; R = (N%2==1?N:N-1)/2 , M;
  113.     while(L<R)
  114.     {
  115.         M = L + (R-L+1)/2;
  116.         if(obj1.check(M*2+1,N))
  117.             L = M ;
  118.         else
  119.             R = M - 1;
  120.     }
  121.     cout<<max(L*2+1,ans);
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
5
ababa
stdout
copy 
5
https://ideone.com/1D8tAF
language:
C++14 (gcc 8.3)
created:
9 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!