Longest Common Substring II

?SPOJ - LCS2?

求10個串的LCS

/*1、用第一個串建立后綴自動機2、len[s] 表示狀態(tài)s 所能代表的字符串的最大長度mx[s] 表示狀態(tài)s 在 當(dāng)前匹配的串的最長匹配后綴長度ans[s] 表示狀態(tài)s 在所有串的最長匹配后綴長度3、用第2——第10個串在后綴自動機上跑，每次mx[s]=max（mx[s]，當(dāng)前匹配長度）每一個串跑完之后，更新 ans[s]=min(ans[s],mx[s])4、每次匹配完一個字符串的時候，要 從后綴自動機 parent 樹 上的葉子節(jié)點 向根更新，因為后綴自動機的parent樹上，min[s]=max(fa[s])+1,所以子節(jié)點能匹配的長度 比 父節(jié)點的max要長。父節(jié)點是子節(jié)點的后綴，父節(jié)點可以匹配子節(jié)點的后max（fa[s]）位，但是在那串在后綴自動機上跑的時候，不能保證經(jīng)過 s 的 時候 也經(jīng)過了s到根的鏈。所以只要子節(jié)點s 有匹配長度，父節(jié)點的mx[fa[s]]即可修改為len[fa[s]]即max（fa[s]） */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 100010 using namespace std; char s[maxn]; int len[maxn<<1],ch[maxn<<1][26],fa[maxn<<1],sz=1,last=1,p,q,np,nq; int c[maxn],sa[maxn<<1],mx[maxn<<1],ans[maxn<<1]; void Insert(int c){np=++sz;len[np]=len[last]+1;ans[sz]=len[sz];p=last;while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];if(!p)fa[np]=1;else {q=ch[p][c];if(len[q]==len[p]+1)fa[np]=q;else {nq=++sz;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];fa[q]=fa[np]=nq;ans[nq]=len[nq]=len[p]+1;while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];}}last=np; } void solve(){int l,c,now,nowlen,x;while(scanf("%s",s+1)!=EOF){l=strlen(s+1);now=1;nowlen=0;for(int i=1;i<=l;i++){c=s[i]-'a';while(now&&!ch[now][c]){now=fa[now];nowlen=len[now];}if(!now){nowlen=0;now=1;}else if(ch[now][c]){nowlen++;now=ch[now][c];}mx[now]=max(mx[now],nowlen);}for(int i=sz;i;i--){x=sa[i];ans[x]=min(ans[x],mx[x]);if(fa[x]&&mx[x])mx[fa[x]]=len[fa[x]];mx[x]=0;}}int Ans=0;for(int i=1;i<=sz;i++)Ans=max(Ans,ans[i]);printf("%d",Ans); } int main(){freopen("Cola.txt","r",stdin);scanf("%s",s+1);int l=strlen(s+1);for(int i=1;i<=l;i++)Insert(s[i]-'a');for(int i=1;i<=sz;i++)c[len[i]]++;for(int i=1;i<=l;i++)c[i]+=c[i-1];for(int i=sz;i;i--)sa[c[len[i]]--]=i;solve();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/thmyl/p/8779164.html

總結(jié)

以上是生活随笔為你收集整理的spoj Longest Common Substring II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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