LCS – Longest Common Substring&&Longest Common Substring II（后缀自动机）
Posted On 2018年12月13日
LCS2 – Longest Common Substring II
Solution
对于parent树记得上传答案，每一次对于子树取max，对自己的长度取min（即拓扑排序一下更新祖先），然后每次的答案取min，最后扫一遍即可
|
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 66 67 68 69 70 71 72 73 74 75 |
#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=2500010*2,inf=1e9; struct sam{int len,fa,trans[26];}st[maxn]; int tott=1,now=1,root=1,tot,ans[maxn],pre[maxn],degree[maxn],q[maxn]; char s[maxn]; inline int max(const int a,const int b){return a>b?a:b;} inline int min(const int a,const int b){return a<b?a:b;} inline void extend(const int ch) { int np=++tott,p=now; st[np].len=st[p].len+1;now=np; while (p&&!st[p].trans[ch])st[p].trans[ch]=np,p=st[p].fa; if (!p)st[np].fa=root; else { int q=st[p].trans[ch]; if (st[p].len+1==st[q].len)st[np].fa=q; else { int nq=++tott; st[nq]=st[q]; st[nq].len=st[p].len+1; st[np].fa=st[q].fa=nq; while (p&&st[p].trans[ch]==q)st[p].trans[ch]=nq,p=st[p].fa; } } } int main() { memset(pre,0x3f,sizeof(pre)); scanf("%s",s+1); int n=strlen(s+1); for (int i=1;i<=n;i++)extend(s[i]-'a'); while (scanf("%s",s+1)!=EOF) { n=strlen(s+1); int cur=1,len=0; for (int i=1;i<=n;i++) { int ch=s[i]-'a'; if (st[cur].trans[ch])cur=st[cur].trans[ch],ans[cur]=max(ans[cur],++len); else { while (!st[cur].trans[ch]&&cur!=root)cur=st[cur].fa; if (st[cur].trans[ch])ans[st[cur].trans[ch]]=max(len=st[cur].len+1,ans[st[cur].trans[ch]]),cur=st[cur].trans[ch]; else len=0; } } int front=1,rear=0; for (int i=1;i<=tott;i++)degree[i]=0; for (int i=1;i<=tott;i++)degree[st[i].fa]++; for (int i=1;i<=tott;i++)if (!degree[i])q[++rear]=i; while (front<=rear) { cur=q[front++]; ans[st[cur].fa]=min(max(ans[cur],ans[st[cur].fa]),st[st[cur].fa].len); if (!--degree[st[cur].fa]&&st[cur].fa)q[++rear]=st[cur].fa; } for (int i=1;i<=tott;i++)pre[i]=min(pre[i],ans[i]),ans[i]=0; } int aw=0; for (int i=1;i<=tott;i++)aw=max(aw,pre[i]); printf("%d\n",aw); } |
Subscribe
0 评论