Description
字符串拆分
Code
#include<bits/stdc++.h> #define ULL unsigned long long #define N 500007 #define Ha 100000007 using namespace std; unordered_map<ULL,int> mp; ULL pre[N],Bas[N]; ULL pos(int st,int len){ return pre[st+len-1]-pre[st-1]*Bas[len]; } bool pan(int st,int len,int edg){ static ULL has; return has=pos(st,len),mp.count(has)&&mp[has]>=edg; } bool gao(int st,int len) { static ULL has; static bool oo; has=pos(st,len); // cout<<has<<endl; if (mp.count(has)) return 1; mp[has]=st; return 0; // return has=pos(st,len),cout<<has<<endl,oo=mp.count(has),mp[has]=max(st,mp,oo; } int n,dp[N],opk,ans;char p[N]; signed main() { // freopen("6.txt","r",stdin); scanf("%d",&n); scanf("%s",p+1); mp[0]=n+1; Bas[0]=1; for (int i=1;i<=n;i++) { pre[i]=pre[i-1]*Ha+p[i]-'a'+1; Bas[i]=Bas[i-1]*Ha; } dp[n+1]=0; for (int i=n;i;i--) { opk=dp[i+1]+2; do {opk--;} while (!pan(i,opk-1,i+opk)&&!pan(i+1,opk-1,i+opk)); dp[i]=opk; ans=max(ans,opk); for (int j=opk;j;j--) if (gao(i,j)) break; } return printf("%d ",ans),0; }