51nod 1277 字符串中的最大值

传送门 又是一道kmp模板题。 运用next数组，我们可以得到一个前缀的最长border 这样串A整个串里出现的次数就是以串A为border的前缀个数。 而可以通过next数组转移到A的都以串A为border 所以我们倒推退出个数，取max即可。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> #define N 100005 using namespace std; char a[N]; int n,t,nxt[N],cnt[N]; int main(){ scanf("%s",a+1); n=strlen(a+1); for (int i=2;i<=n;i++){ while (t&&a[i]!=a[t+1]) t=nxt[t]; if (a[i]==a[t+1]) t++; nxt[i]=t; cnt[t]++; } long long ans=0; for (int i=n;i>=1;i--){ ans=max(ans,(long long)(cnt[i]+1)*i); cnt[nxt[i]]+=cnt[i]; } printf("%lld",ans); }