正題

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

---

題目大意

一個字符串，求最大的回文串長度×出現(xiàn)次數(shù)

---

解題思路

構(gòu)建出$\text{PAM}$然后統(tǒng)計一下每個節(jié)點作為后綴的次數(shù)，$fail$樹上上傳一下信息就好了，時間復(fù)雜度$O(n)$。

當(dāng)然也可以$\text{SAM}+\text{Manacher}+$倍增，因為一個字符串里本質(zhì)不同的回文串就是會讓馬拉車的$maxright$增加的回文串，這些最多只有$n$個，馬拉車跑出來的丟到$\text{SAM}$倍增找到對應(yīng)節(jié)點即可。時間復(fù)雜度$O(n\log n)$

這里寫的是$\text{PAM}$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e5+10; int n,tot,fail[N],len[N],cnt[N],ch[N][26]; char s[N];long long ans; int get_fail(int x,int n){for(;s[n-len[x]-1]!=s[n];)x=fail[x];return x; } int Insert(int n,int x){x=get_fail(x,n);int c=s[n]-'a';if(!ch[x][c]){len[++tot]=len[x]+2;int y=get_fail(fail[x],n);fail[tot]=ch[y][c];ch[x][c]=tot;}cnt[ch[x][c]]++;return ch[x][c]; } int main() {scanf("%s",s+1);n=strlen(s+1);int last=0;len[1]=-1;fail[0]=tot=1;for(int i=1;i<=n;i++)last=Insert(i,last);for(int i=tot;i>=1;i--)cnt[fail[i]]+=cnt[i];for(int i=1;i<=tot;i++)ans=max(ans,1ll*len[i]*cnt[i]);printf("%lld\n",ans); }

總結(jié)

以上是生活随笔為你收集整理的P3649-[APIO2014]回文串【PAM】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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