結果
問題 | No.765 ukuku 2 |
ユーザー |
![]() |
提出日時 | 2019-02-22 18:34:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 3,000 ms |
コード長 | 2,593 bytes |
コンパイル時間 | 2,009 ms |
コンパイル使用メモリ | 198,672 KB |
最終ジャッジ日時 | 2025-01-06 21:26:15 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}struct RollingHash{using ull = unsigned long long;vector<ull> hash,p;RollingHash(){}RollingHash(const string &s,ull B=1000000007LL){int n=s.size();hash.assign(n+1,0);p.assign(n+1,1);for(int i=0;i<n;i++){hash[i+1]=hash[i]*B+s[i];p[i+1]=p[i]*B;}}//S[l, r)ull find(int l,int r){return hash[r]-hash[l]*p[r-l];}};//INSERT ABOVE HEREsigned main(){string s;cin>>s;int n=s.size();string t(s);reverse(t.begin(),t.end());if(s==t){cout<<n-1<<endl;return 0;}RollingHash rhs(s),rht(t);int ans=0;// oddfor(int i=0;i<n;i++){int l=0,r=min(i,n-(i+1))+1;while(l+1<r){int m=(l+r)>>1;auto x=rhs.find(i+1,i+1+m);auto y=rht.find(n-i,n-i+m);if(x==y) l=m;else r=m;}if(l==min(i,n-(i+1))){chmax(ans,l*2+1);continue;}int pl=l,pr=r;{l=pl;r=pr;int p=l;r=min(i,n-(i+2))+1;while(l+1<r){int m=(l+r)>>1;auto x=rhs.find(i+2+p,i+2+m);auto y=rht.find(n-i+p,n-i+m);if(x==y) l=m;else r=m;}chmax(ans,l*2+1);}{l=pl;r=pr;int p=l;r=min(i-1,n-(i+1))+1;while(l+1<r){int m=(l+r)>>1;auto x=rhs.find(i+1+p,i+1+m);auto y=rht.find(n-i+p+1,n-i+m+1);if(x==y) l=m;else r=m;}chmax(ans,l*2+1);}}// evenfor(int i=0;i+1<n;i++){if(s[i]!=s[i+1]) continue;int l=0,r=min(i,n-(i+2))+1;while(l+1<r){int m=(l+r)>>1;auto x=rhs.find(i+2,i+2+m);auto y=rht.find(n-i,n-i+m);if(x==y) l=m;else r=m;}if(l==min(i,n-(i+2))){chmax(ans,l*2+2);continue;}int pl=l,pr=r;{l=pl;r=pr;int p=l;r=min(i,n-(i+3))+1;while(l+1<r){int m=(l+r)>>1;auto x=rhs.find(i+3+p,i+3+m);auto y=rht.find(n-i+p,n-i+m);if(x==y) l=m;else r=m;}chmax(ans,l*2+2);}{l=pl;r=pr;int p=l;r=min(i-1,n-(i+2))+1;while(l+1<r){int m=(l+r)>>1;auto x=rhs.find(i+2+p,i+2+m);auto y=rht.find(n-i+p+1,n-i+m+1);if(x==y) l=m;else r=m;}chmax(ans,l*2+2);}}cout<<ans<<endl;return 0;}