首页 > 代码库 > 【后缀自动机】SPOJ 1812-LCSII
【后缀自动机】SPOJ 1812-LCSII
题意：
给出最多10个长度不超过100000的字符串，求他们的LCS的长度。时限是鬼畜的0.25s 。
后缀自动机练习...
虽然有人这么说但我并不觉得hash能过。
本题可以说是【论SAM中按step排序更新pre的重要性】：
总的来说做法和1811-LCS有点类似，不同的是因为有多个字符串，因此每个字符串都需要在SAM上跑一次。
记录下每个节点最长能容纳长度为多少的字符，最后取个MAX就行了。
用nans[i]表示匹配当前字符串时，i号点能容纳的子串长度，如果i的pre上的当前答案比i还要小的话就用nans[i]来更新nans[i.pre] 。
用ans表示所有nans的最小值，在计算每个字符串时用nans来更新ans，最后在ans中找一个MAX就可以了。
一开始忘记了黑体的那句话，结果拍了很久又没拍出来，提交的时候在第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 else20 {21 int q = Suf[p].s[nxt];22 if (step[q] == step[p] + 1) Suf[now].pre = q;23 else24 {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 else64 {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-LCSII
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。