題意：

　　給出最多10個長度不超過100000的字符串，求他們的LCS的長度。時限是鬼畜的0.25s 。

?

后綴自動機練習(xí)...雖然有人這么說但我并不覺得hash能過。

?

本題可以說是【論SAM中按step排序更新pre的重要性】：

　　總的來說做法和1811-LCS有點類似，不同的是因為有多個字符串，因此每個字符串都需要在SAM上跑一次。

　　記錄下每個節(jié)點最長能容納長度為多少的字符，最后取個MAX就行了。

?

　　用nans[i]表示匹配當(dāng)前字符串時，i號點能容納的子串長度，如果i的pre上的當(dāng)前答案比i還要小的話就用nans[i]來更新nans[i.pre] 。

　　用ans表示所有nans的最小值，在計算每個字符串時用nans來更新ans，最后在ans中找一個MAX就可以了。

?

一開始忘記了黑體的那句話，結(jié)果拍了很久又沒拍出來，提交的時候在第10個點WA了簡直難過...

?

1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #define maxn 105000*2 6 using namespace std; 7 8 struct node { int s[26],pre; } Suf[maxn]; 9 char S[maxn],T[maxn]; 10 int i,j,n,m,k,len1,len2,len,last = 1,root = 1,cnt = 1; 11 int step[maxn],nans[maxn],ans[maxn],f[maxn]; 12 13 void add(int nxt) 14 { 15 int now = ++cnt, p = last; 16 step[now] = step[p] + 1; 17 for ( ; p != 0 && Suf[p].s[nxt] == 0; p = Suf[p].pre) Suf[p].s[nxt] = now; 18 if (p == 0) Suf[now].pre = root; 19 else 20 { 21 int q = Suf[p].s[nxt]; 22 if (step[q] == step[p] + 1) Suf[now].pre = q; 23 else 24 { 25 int nq = ++cnt; 26 step[nq] = step[p] + 1; 27 Suf[nq] = Suf[q]; 28 Suf[q].pre = Suf[now].pre = nq; 29 for ( ; p != 0 && Suf[p].s[nxt] == q; p = Suf[p].pre) Suf[p].s[nxt] = nq; 30 } 31 } 32 last = now; 33 } 34 35 bool cmp(int a,int b) { return step[a] < step[b]; } 36 37 int main() 38 { 39 scanf("%s\n",S+1); 40 len1 = strlen(S+1); 41 for (i = 1; i <= len1; i++) add(S[i]-'a'); 42 43 for (i = 1; i <= cnt; i++) f[i] = i; 44 stable_sort(f+1,f+1+cnt,cmp); 45 46 memcpy(ans,step,sizeof(ans)); 47 48 while (scanf("%s\n",T+1) != EOF) 49 { 50 memset(nans,0,sizeof(nans)); 51 52 len2 = strlen(T+1); 53 int now = root,len = 0; 54 for (i = 1; i <= len2; i++) 55 { 56 int nxt = T[i]-'a'; 57 if (Suf[now].s[nxt] != 0) 58 { 59 len++; 60 now = Suf[now].s[nxt]; 61 nans[now] = max(nans[now],len); 62 } 63 else 64 { 65 while (Suf[now].s[nxt] == 0 && now != 0) now = Suf[now].pre; 66 if (now == 0) now = root,len = 0; 67 else len = step[now] + 1,now = Suf[now].s[nxt],nans[now] = max(nans[now],len); 68 } 69 } 70 for (i = cnt; i >= 1; i--) 71 { 72 ans[f[i]] = min(ans[f[i]],nans[f[i]]); 73 nans[Suf[f[i]].pre] = max(nans[Suf[f[i]].pre],nans[f[i]]); 74 } 75 } 76 77 int ANS = 0; 78 for (i = 1; i <= cnt; i++) 79 ANS = max(ANS,ans[i]); 80 81 printf("%d\n",ANS); 82 return 0; 83 } SPOJ 1812

?

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

總結(jié)

以上是生活随笔為你收集整理的【后缀自动机】SPOJ 1812-LCSII的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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