Description

　　有一個(gè)文件被破壞了，可是值得慶幸的是，只是文件的順序被打亂了。文件僅包含大小寫(xiě)的拉丁字母以及逗號(hào)，句號(hào)和嘆號(hào)。為了盡快修復(fù)，請(qǐng)你找出有多少個(gè)至少出現(xiàn)兩次的子串。
　　比如字符串a(chǎn)bbabc，子串”a”，”b”,”ab”分別出現(xiàn)了2次，3次，2次。

Input

　　輸入文件第一行包含一個(gè)整數(shù)n表示文件的長(zhǎng)度。
　　第二行n個(gè)字符，表示被破壞的文件。

Output

　　輸出一個(gè)數(shù)，表示有多少個(gè)至少出現(xiàn)兩次的子串。

Sample Input

aabbabb

Sample Output

5

Data Constraint

Hint

【數(shù)據(jù)約束和評(píng)分方法】

　　對(duì)于10%的數(shù)據(jù)，1<=n<=100。
　　對(duì)于30%的數(shù)據(jù)，1<=n<=1000。
　　對(duì)于50%的數(shù)據(jù)，1<=n<=10000。　　
　　對(duì)于100%的數(shù)據(jù)，1<=n<=100000。

Solution

-這題是最經(jīng)典的后綴數(shù)組（Suffix Array，SA），直接上模板啦。

• 對(duì)于如何處理“至少出現(xiàn)兩次的子串”，我們可以先處理出 Height 數(shù)組，

• 接著用 Height[i]-Height[i-1] 求出第 i 項(xiàng)的答案，就像容斥一樣，累加即可。

Code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100005; int n,m=127,ans; int sa[N],rank[N],height[N],tax[N],tp[N]; char s[N]; void Csort() {for(int i=0;i<=m;i++) tax[i]=0;for(int i=1;i<=n;i++) tax[rank[i]]++;for(int i=1;i<=m;i++) tax[i]+=tax[i-1];for(int i=n;i;i--) sa[tax[rank[tp[i]]]--]=tp[i]; } bool cmp(int x,int y,int l) {return tp[x]==tp[y] && tp[x+l]==tp[y+l]; } void Suffix_Array() {for(int i=1;i<=n;i++) rank[tp[i]=i]=s[i];Csort();for(int len=1,p=0;len<=n;len<<=1,m=p,p=0){for(int i=n-len+1;i<=n;i++) tp[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>len) tp[++p]=sa[i]-len;Csort(),swap(rank,tp);rank[sa[1]]=p=1;for(int i=2;i<=n;i++)rank[sa[i]]=cmp(sa[i],sa[i-1],len)?p:++p;if(p==n) break;}for(int i=1,lcp=0;i<=n;height[rank[i++]]=lcp){if(lcp) lcp--;while(s[i+lcp]==s[sa[rank[i]-1]+lcp]) lcp++;} } int main() {scanf("%s",s+1);n=strlen(s+1);Suffix_Array();for(int i=2;i<=n;i++) ans+=max(height[i]-height[i-1],0);printf("%d",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 1598. 文件修复的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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