LCS - Longest Common Substring
spoj1811
sam--后缀自动机裸题 。
把a串建立后缀自动机，然后对于b串跑一遍就好了，遇到跑不动的就返回pre继续跑
c++代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <bits/stdc++.h> #define rep(i,x,y) for(register int i = x ;i <= y; ++i) #define max(x,y) (x > y ? x : y) const int N = 3e5+500; struct node{ int ch[26],pre,len; }t[N << 1]; int sz = 1,root = 1,last = 1; void insert(int x) { int p = last,np = ++sz; t[np].len = t[p].len + 1; for(; p && !t[p].ch[x];p = t[p].pre) t[p].ch[x] = np; if( !p ) t[np].pre = root; else { int q = t[p].ch[x]; if(t[q].len == t[np].len + 1) t[np].pre = q; else { int nq = ++sz; t[nq] = t[q]; t[nq].len = t[p].len + 1; t[q].pre = t[np].pre = nq; for(;p && t[p].ch[x] == q;p = t[p].pre) t[p].ch[x] = nq; } } last = np; } char s1[N],s2[N]; int solve() { int len = strlen(s2),ans = 0,now = 0,p = root; rep(i,0,len- 1) { if(t[p].ch[s2[i] - 'a']) now ++,p = t[p].ch[s2[i] - 'a']; else { for(;p && !t[p].ch[s2[i] - 'a']; p = t[p].pre) ; if(!p) p = root,now = 0; else now = t[p].len + 1,p = t[p].ch[s2[i] - 'a']; } ans = max(ans,now); } return ans; } int main() { scanf("%s%s",s1,s2); int len = strlen(s1); rep(i,0,len - 1) insert(s1[i] - 'a'); printf("%d\n",solve()); return 0; } |