BZOJ2803: [Poi2012]Prefixuffix

2019-11-06 06:24:55

字體：大中小

來源：轉載

供稿：網友

有個很厲害的性質，推出了這個就可以DP了

有了這個DP，就可以枚舉找一個最大值了這題好像需要雙hash

code：

#include<map>#include<set>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long longusing namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}void up(int &x,int y){if(x<y)x=y;}const int maxn = 1100000;const ll Mod=1e9+7;char str[maxn];int f[maxn];ll h[maxn],hk=233,h2[maxn],hk2=1e8+7;ll pw[maxn],pw2[maxn];int n,m;bool judge(int l,int r,int l2,int r2){ ll s1=h[r]-h[l-1]*pw[r-l+1]; ll s2=h[r2]-h[l2-1]*pw[r2-l2+1]; if(s1!=s2) return false; s1=h2[r]-h2[l-1]*pw2[r-l+1]%Mod; s2=h2[r2]-h2[l2-1]*pw2[r-l+1]%Mod; s1=(s1%Mod+Mod)%Mod; s2=(s2%Mod+Mod)%Mod; return s1==s2;}void g_f(){ int mi=n>>1; int k=0; for(int i=mi;i>=1;i--) { k+=2; while(i+k-1>mi)k--; while(k&&!judge(i,i+k-1,n-i+1-k+1,n-i+1)) k--; f[i]=k; }}int main(){ read(n); scanf("%s",str+1); for(int i=1;i<=n;i++) h[i]=h[i-1]*hk+str[i]-'a'; for(int i=1;i<=n;i++) h2[i]=(h2[i-1]*hk2+str[i]-'a')%Mod; pw[0]=1ll; for(int i=1;i<=n;i++) pw[i]=pw[i-1]*hk; pw2[0]=1ll; for(int i=1;i<=n;i++) pw2[i]=pw2[i-1]*hk2%Mod; g_f(); int L=0; int mi=n>>1; for(int i=n;i>=n-mi+1;i--) if(judge(i,n,1,n-i+1)) up(L,(n-i+1)+f[n-i+2]);