正題

題目鏈接:https://www.luogu.com.cn/problem/P3804

---

題目大意

長(zhǎng)度為$n$的串，求一個(gè)出現(xiàn)次數(shù)不小于2的子串使得子串長(zhǎng)度乘上出現(xiàn)次數(shù)最大。

---

解題思路

構(gòu)建$SAM$的時(shí)候統(tǒng)計(jì)一下每個(gè)子串出現(xiàn)多少次即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e6+10; int n,cnt,num[N],len[N],fail[N],next[N][26],ans; char s[N]; void New_Point(int x,int y){next[x][y]=++cnt;len[cnt]=len[x]+1; } void Make_SAM(char *s){int last;cnt=last=num[1]=1;for(int i=1;i<=n;i++){int val=s[i]-'a';New_Point(last,val);int x=last,y;last=next[x][val];for(y=fail[x];y;y=fail[y])if(!next[y][val]) next[y][val]=last;else{if(len[y]+1==len[next[y][val]])fail[last]=next[y][val];else{int z=next[y][val];New_Point(y,val);fail[cnt]=fail[z];num[cnt]=num[z];fail[last]=fail[z]=cnt;for(int i=0;i<26;i++)next[cnt][i]=next[z][i];for(int w=y;w;w=fail[w])if(next[w][val]==z)next[w][val]=cnt;}break;}if(!y)fail[last]=1;for(y=last;y;y=fail[y])num[y]++;}return; } int main() {scanf("%s",s+1);n=strlen(s+1);Make_SAM(s);for(int i=1;i<=cnt;i++)if(num[i]>1)ans=max(ans,num[i]*len[i]);printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的P3804-[模板]后缀自动机【SAM】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。