首页 > 代码库 > SPOJ 1812 LCS2 [后缀自动机]
SPOJ 1812 LCS2 [后缀自动机]
题意：
求多个串<=10的最长连续子串
一个串建SAM，然后其他串在上面走
每个状态记录所有串在这个状态的公共子串的最小值
一个串在上面走的时候记录与每个状态公共子串的最大值，注意出现次数向父亲传递，一个状态能到达说明了Suffix Link指向的状态可以取到最大子串，这一步对val后基数排序然后倒着更新就行了
注意两点：
1.空间要开两倍，基数排序用的东西也要两倍哦
2.答案不能用mn[1]更新！！！！因为mn[1]没有意义啊root状态一个子串也没有还可能有某些bug
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=2e5+5;int n,m;char s[N];struct State{ int ch[26],par,val;}t[N<<1];int sz,root,last;inline int nw(int _){t[++sz].val=_;return sz;}void iniSAM(){sz=0;root=last=nw(0);}void extend(int c){ int p=last,np=nw(t[p].val+1); while(p&&t[p].ch[c]==0) t[p].ch[c]=np,p=t[p].par; if(p==0) t[np].par=root; else{ int q=t[p].ch[c]; if(t[q].val==t[p].val+1) t[np].par=q; else{ int nq=nw(t[p].val+1); memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch)); t[nq].par=t[q].par; t[q].par=t[np].par=nq; while(p&&t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].par; } } last=np;}int mx[N<<1],mn[N<<1];void walk(char s[]){ int sum=0,u=root,n=strlen(s+1); for(int i=1;i<=n;i++){ int c=s[i]-‘a‘; if(t[u].ch[c]) u=t[u].ch[c],mx[u]=max(mx[u],++sum); else{ while(u&&!t[u].ch[c]) u=t[u].par; if(!u) u=root,sum=0; else sum=t[u].val,u=t[u].ch[c],mx[u]=max(mx[u],++sum); } }}int c[N<<1],a[N<<1],ans;void RadixSort(int len){ for(int i=1;i<=sz;i++) c[t[i].val]++; for(int i=1;i<=len;i++) c[i]+=c[i-1]; for(int i=sz;i>=1;i--) a[c[t[i].val]--]=i; for(int i=1;i<=sz;i++) mn[i]=t[i].val;}void solve(){ iniSAM(); scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;i++) extend(s[i]-‘a‘); RadixSort(len); while(scanf("%s",s+1)!=EOF){ walk(s); for(int j=sz;j>=1;j--){ int u=a[j]; mn[u]=min(mn[u],mx[u]); if(mx[u]&&t[u].par) mx[t[u].par]=t[t[u].par].val; mx[u]=0; } } for(int i=2;i<=sz;i++) ans=max(ans,mn[i]); printf("%d",ans);}int main(){ //freopen("in","r",stdin); solve();}
SPOJ 1812 LCS2 [后缀自动机]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。