首页 > 代码库 > Codeforces 427D Match & Catch（后缀自动机）
Codeforces 427D Match & Catch（后缀自动机）
【题目链接】 http://codeforces.com/problemset/problem/427/D
【题目大意】
给出一个两个字符串，求出最短且在两个字符串中唯一的公共子串。
【题解】
以原字符串的两倍建立自动机，按字典序在parent树上搜索，
得到的第一个长度为n的字符串就是答案。
【代码】
#include <cstdio>#include <cstring>#include <algorithm> #include <vector>using namespace std;const int N=40005;char s[N];struct sam{ int p,q,np,nq,cnt,last,a[N][26],l[N],f[N]; sam(){cnt=0;last=++cnt;} void init(){ cnt=0;last=++cnt; memset(a,0,sizeof(a)); memset(l,0,sizeof(l)); memset(f,0,sizeof(f)); } void extend(int c){ p=last;np=last=++cnt;l[np]=l[p]+1; while(!a[p][c]&&p)a[p][c]=np,p=f[p]; if(!p)f[np]=1; else{ q=a[p][c]; if(l[p]+1==l[q])f[np]=q; else{ nq=++cnt;l[nq]=l[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); f[nq]=f[q]; f[np]=f[q]=nq; while(a[p][c]==q)a[p][c]=nq,p=f[p]; } } } void solve(){ init(); scanf("%s",s); int n=strlen(s),len=n; for(int k=0;k<2;k++)for(int i=0;i<n;i++)extend(s[i]-‘a‘); int p=1; while(n--){ for(int i=0;i<26;i++)if(a[p][i]){ p=a[p][i];break; } }printf("%d\n",l[p]-len+1); }}sam;int T;int main(){ scanf("%d",&T); while(T--)sam.solve(); return 0;}
Codeforces 427D Match & Catch（后缀自动机）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。