【SPOJ1811】Longest Common Substring
构造出SAM以后就可以直接做了，和KMP很像。
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 59 60 61 62 63 64 65 | #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=250010;struct SAM{ struct State { int next[26]; int link; int len; }st[maxn<<1]; int cnt; int last; SAM() {last=cnt=1;} void Extend(int c) { int x=++cnt,p; st[x].len=st[last].len+1; for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x; if (!p) st[x].link=1; else { int q=st[p].next[c]; if (st[p].len==st[q].len-1) st[x].link=q; else { int v=++cnt; st[v]=st[q]; st[v].len=st[p].len+1; for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v; st[q].link=st[x].link=v; } } last=x; } int LCS(char *ch,int n) { int res=0; for (int i=0,p=1,len=0;i<n;i++) { int c=ch[i]-'a'; while (p && !st[p].next[c]) p=st[p].link,len=st[p].len; if (!p) p=1,len=0;else p=st[p].next[c],len++; res=max(res,len); } return res; }}M;char ch[maxn];int n;int main(){ scanf("%s",ch); n=strlen(ch); for (int i=0;i<n;i++) M.Extend(ch[i]-'a'); scanf("%s",ch); printf("%d\n",M.LCS(ch,strlen(ch))); return 0;} |
评论 (0)
