fork download
copy 
  1. /// Manacher by muoii
  2.  
  3. /// vn.spoj.com/problems/PALINY/
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define tag "spoj"
  7. #define maxn 100007
  8. #define oo 1000000007
  9. #define mid ((l+r)>>1)
  10. #define meset(a,x) memset(a,x,sizeof(a))
  11. #define loop(x) for(int LoOpEr=1;LoOpEr<=x;LoOpEr++)
  12. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  13. void manacher(const string &str,vector<int> &mana)
  14. {
  15.     int n=2*str.size()+1;
  16.     string s=string(n,'#');
  17.     for(int i=1;i<n;i+=2) s[i]=str[i/2];
  18.  
  19.     mana.resize(n);
  20.     int l=0,r=0;
  21.     for(int i=0;i<n;i++)
  22.     {
  23.         mana[i]=(i<r)?min(r-i,mana[2*l-i]):0;
  24.         while(s[i-mana[i]-1]==s[i+mana[i]+1]) ++mana[i];
  25.         if(i+mana[i]>r) r=(l=i)+mana[i];
  26.     }
  27. }
  28.  
  29. bool palin(const int &l,const int &r,const vector<int> &mana)
  30. {
  31.     return (l<r)?0:mana[l+r+1]>=(r-l+1);
  32. }
  33.  
  34. int main()
  35. {
  36.     #ifdef dmdd
  37.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  38.     #endif //dmdd
  39.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  40.  
  41.     int n; string s;vector<int> f;
  42.     cin>>n>>s;
  43.     manacher(s,f);
  44.  
  45.     cout<<*max_element(f.begin(),f.end());
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0s 4324KB
comments (?)
stdin
copy 
5
abacd
stdout
copy 
3
https://ideone.com/qOs5mt
language:
C++ (gcc 8.3)
created:
6 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!