这题是后缀自动机一眼题，但是我们有更简洁的方法解决它
我们回想kmp算法，一个串在进行自我匹配时j指针所在的位置正好是长度为j的前缀，每次匹配长度为j的前缀都被匹配上了一次
我们只需要记录每次j指针的位置，然后cnt[j]++就能统计次数
博主刚开始就是这么干的，结果样例都过不了
经过手玩推导，博主发现在长度为j的前缀被匹配到的同时，可能出现长度小于j的前缀也匹配到了的情况
博主不会处理这种情况于是去翻大佬题解
在某篇博客中提到了一个叫做next树的东西，就像AC自动机fail树一样，kmp中的next指针也形成了一棵树
所以要按照顺序沿着next树更新cnt数组，长知识了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 1000010 #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) using namespace std; typedef long long ll; int n,pre[MAXN],cnt[MAXN]; char ch[MAXN]; int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); scanf("%s",ch+1); n=strlen(ch+1); ll ans=0; for(int i=2,j=0;i<=n;++i){ while(ch[j+1]!=ch[i]&&j) j=pre[j]; if(ch[j+1]==ch[i]) ++j; pre[i]=j; cnt[j]++; } for(int i=n;i;--i){ cmax(ans,(ll)(cnt[i]+1)*i); cnt[pre[i]]+=cnt[i]; } printf("%lld\n",ans); return 0; }
|