題目鏈接：點(diǎn)擊查看

題目大意：

蒜斜剛來PKU的時(shí)候還不知道有“北大算協(xié)”這個(gè)社團(tuán)，因此他總是覺得周圍的人在偷偷議論著他，比如說：

“算協(xié)（注：非蒜斜）舉辦的活動(dòng)好有趣啊！”

“算協(xié)（注：非蒜斜）好帥啊！”

蒜斜每次聽到這些話就會(huì)想入非非，但仔細(xì)想想，自己好像也沒有那么帥吧？最離譜的一次還是：

“算協(xié)（注：非蒜斜）有好多小哥哥”（霧）

自從蒜斜學(xué)習(xí)了半前綴之后，他把這些話都看開了 —— 對他來說，只要這些話里有 “蒜斜好” 的半前綴就足夠了。

題目描述

設(shè)小寫字母字符串?s, 長度為?n,?s[l:r] 表示第?l?個(gè)到第?r?個(gè)字符構(gòu)成的子串,?l>r 時(shí)對應(yīng)空串。

定義半前綴是?s[1:i]+s[j:k], 其中?0≤i<len(s),i<j≤len(s),j?1≤k≤len(s)。直觀上來說，你可以把半前綴理解成某一個(gè)前綴?s[1:k]刪除掉某一個(gè)子串后形成的結(jié)果（當(dāng)然也允許不刪）。

給出字符串?ss，你需要求出?ss?的所有半前綴中，有多少個(gè)不同的字符串。

輸入格式

輸入一行包含一個(gè)小寫字符串?s(1≤|s|≤106)。

輸出格式

輸出一行一個(gè)整數(shù)，表示答案。

樣例一

input

aab

output

6

explanation

字符串?aab?的半前綴有：空串，a，b，aa，ab，aab。

樣例二

input

pkusaamtcup

output

217

限制與約定

Small Task:?|s|≤3000。

Large Task:?|s|≤106。

時(shí)間限制：2s

空間限制：512MB

題目分析：讀完題后第一反應(yīng)就是后綴自動(dòng)機(jī)，但是需要猜結(jié)論或者變形，然后就止步于此了

賽后看了jls的講題視頻豁然開朗，感覺這個(gè)題目太妙了

首先因?yàn)轭}目規(guī)定的半前綴是一個(gè)前綴與一個(gè)子串拼接而成，對于每個(gè)半前綴而言，肯定有很多的拼接方法，如果不加以約束的話，很容易重復(fù)統(tǒng)計(jì)，對于每個(gè)半前綴 s[ 0 : i ] + s[ j : k ] 我們只計(jì)算 i 最大的那個(gè)半前綴這樣就能做到不重不漏了

該如何確定某個(gè)半前綴已經(jīng)是 i 最大的呢，一個(gè)必要條件是 s[ i + 1 ] != s[ j ] ，這個(gè)比較容易看出來，因?yàn)槿绻?s[ i + 1 ] == s[ j ] 的話，那么顯然 s[ 0 : i + 1 ] + s[ j + 1 : k ] 是一個(gè)比 i 更靠后的半前綴，所以必要性成立

接下來證明一下充分性，假設(shè)有更靠后的一個(gè)半前綴 s[ 0 : i' ] + s[ j' : k' ] 滿足 i < i' ，因?yàn)?s[ 0 : i ] + s[ j : k ] ==?s[ 0 : i' ] + s[ j' : k' ] ，所以 s[ i + 1 : i' ] == s[ j?: j?+ [一段區(qū)間] ] ，即 s[ i + 1 ] == s[ j ] ，與上面的結(jié)論相悖，所以證明了充分性

綜上，s[ i + 1 ] != s[ j ] 是?s[ 0 : i ] + s[ j : k ] 作為最后一次出現(xiàn)的半前綴的重分必要條件

那么接下來我們只需要枚舉 i ，然后統(tǒng)計(jì) s[ i + 1 : k ] 中有多少個(gè)首字母不為 s[ i + 1 ] 的本質(zhì)不同子串即可

然后用后綴自動(dòng)機(jī)解決就好了，因?yàn)橐y(tǒng)計(jì)的區(qū)間實(shí)際上為 [ i + 1 , n ] ，所以我們可以倒著插入字符串，因?yàn)樽址诜D(zhuǎn)之后，本質(zhì)不同的子串個(gè)數(shù)是不變的，每次插入后利用 last 指針更新 cnt 數(shù)組，cnt[ j ] 表示截止到目前為止，首字母為 j 的本質(zhì)不同子串有多少個(gè)，將答案累加就好了

最后需要注意的是，初始化為賦值為 n + 1 ，這里的 1 是指空串，而 n 是指形如 [ 1 , 1 ] + 空串，[ 1 , 2 ] + 空串, [ 1 , 3 ] + 空串... + ?[ 1 , n ] + 空串 ，這樣的半前綴，因?yàn)楹缶Y自動(dòng)機(jī)無法統(tǒng)計(jì)空串的個(gè)數(shù)，所以需要我們自己手動(dòng)計(jì)算上空串的貢獻(xiàn)

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;char s[N];LL cnt[26];int tot=1,last=1;struct Node {int ch[26];int fa,len; }st[N<<1];void add(int x) {int p=last,np=last=++tot;st[np].len=st[p].len+1;while(p&&!st[p].ch[x])st[p].ch[x]=np,p=st[p].fa;if(!p)st[np].fa=1;else{int q=st[p].ch[x];if(st[p].len+1==st[q].len)st[np].fa=q;else{int nq=++tot;st[nq]=st[q]; st[nq].len=st[p].len+1;st[q].fa=st[np].fa=nq;while(p&&st[p].ch[x]==q)st[p].ch[x]=nq,p=st[p].fa;//向上把所有q都替換成nq}} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%s",s);int n=strlen(s);LL ans=n+1;for(int i=n-1;i>=0;i--){add(s[i]-'a');cnt[s[i]-'a']+=st[last].len-st[st[last].fa].len;for(int j=0;j<26;j++)if(s[i]-'a'!=j)ans+=cnt[j];}printf("%lld\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的美团杯2020 - 半前缀计数(后缀自动机)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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