首页 > 代码库 > 【后缀自动机】spoj1811-LCS
【后缀自动机】spoj1811-LCS
题意
给你两个字符串，求他们的LCS的长度 N <= 2.5e5 时限0.25s左右
后缀自动机练习...不知道hash行不行我想去试一发。
本题要用到的是后缀自动机的一个性质：
构建自动机时用到的step数组，之前以为是没什么用的，原来还能这样，长知识了。
step[i]表示的是【从root节点走到i这个节点，经过了几个字符】，这个性质在匹配时失配的情况下可以用来更新当前答案。
利用第一个字符串建立一个SAM，然后用第二个字符串来在自动机上进行匹配，看看最长能匹配多远就是答案了。
在失配的时候考虑两种情况：
1，因为now的pre链上的点与now点具有相同的后缀，因此如果都已经匹配到now点了，那么now.pre肯定已经出现过了，因此可以跳到pre上重新匹配。
2，如果一直跳到了0，即整条pre链上都没有当前的字符，所以长度清空，继续匹配。
注意的是每次匹配完之后ans都要对当前的len取一个max。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #define maxn 255000*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,ans;11 int step[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 int main()36 {37 while ( scanf("%s\n%s\n",S+1,T+1) != EOF )38 { 39 memset(Suf,0,sizeof(Suf)); memset(step,0,sizeof(step)); cnt = 1; last = 1; ans = 0;40 len1 = strlen(S+1); len2 = strlen(T+1);41 42 for (i = 1; i <= len1; i++) add(S[i]-‘a‘);43 44 int now = root,len = 0;45 for (i = 1; i <= len2; i++)46 {47 int nxt = T[i]-‘a‘;48 if (Suf[now].s[nxt] != 0) 49 {50 len++;51 now = Suf[now].s[nxt];52 }53 else54 {55 while (Suf[now].s[nxt] == 0 && now != 0) now = Suf[now].pre;56 if (now == 0) now = root,len = 0;57 else len = step[now] + 1,now = Suf[now].s[nxt];58 }59 ans = max(ans,len);60 }61 62 printf("%d\n",ans);63 }64 return 0;65 }
【后缀自动机】spoj1811-LCS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。