http://poj.org/problem?id=2774 (题目链接)
题意
给出两个只包含小写字母的字符串，求出最长连续公共子串。
solution
第一次用后缀数组，感觉有点神。。。才发现原来sa[0]是没用的。。
将两个字符串合并为一个，并用分隔符隔开。之后跑后缀数组，求出height[]，for一遍，找到在分隔符两侧的height值最大的便是答案。
UPD 2017.1.11：
我以前写的什么东西。。贴一个板子，还是习惯下标从1开始→_→
代码
// poj2774
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
#define LL long long
#define inf 1<<30
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int maxn=200010;
int rank[maxn],height[maxn],sa[maxn];
char s[maxn],s1[maxn];
namespace Suffix {
int wa[maxn],wb[maxn],ww[maxn];
int cmp(int *r,int a,int b,int l) {
return r[a]==r[b] && r[a+l]==r[b+l]; //这样写不会造成数组越界
}
void da(char *r,int *sa,int n,int m) {
int i,j,p,*x=wa,*y=wb;
for (i=0;i<=m;i++) ww[i]=0; //将桶清空
for (i=1;i<=n;i++) ww[x[i]=r[i]]++; //x记录名次
for (i=1;i<=m;i++) ww[i]+=ww[i-1]; //前缀和
for (i=n;i>=1;i--) sa[ww[x[i]]--]=i; //从n for到1和从1 for到n都可以
for (p=1,j=1;p<n;j*=2,m=p) { //j代表长度;如果已经有n个排名不同的后缀则完成;排完序后m就等于p
for (p=0,i=n-j+1;i<=n;i++) y[++p]=i; //它们没有第二关键字
for (i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j; //第二关键字排序
for (i=0;i<=m;i++) ww[i]=0; //第一关键字排序
for (i=1;i<=n;i++) ww[x[y[i]]]++;
for (i=1;i<=m;i++) ww[i]+=ww[i-1];
for (i=n;i>=1;i--) sa[ww[x[y[i]]]--]=y[i]; //这里一定要从n for 到1
for (swap(x,y),x[sa[1]]=p=1,i=2;i<=n;i++) //将名次储存在x里面
x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p : ++p;
}
}
void calheight(char *r,int *sa,int n) {
for (int i=1;i<=n;i++) rank[sa[i]]=i;
for (int k=0,i=1;i<=n;i++) {
if (k) k--;
int j=sa[rank[i]-1];
while (s[i+k]==s[j+k]) k++;
height[rank[i]]=k; //注意这里是rank[i]
}
}
}
int main() {
scanf("%s%s",s+1,s1+1);
int n=strlen(s+1);
int n1=strlen(s1+1);
s[++n]='#';int l=n;
for (int i=1;i<=n1;i++) s[n+i]=s1[i];
n+=n1;
using namespace Suffix;
da(s,sa,n,200);
calheight(s,sa,n);
int ans=0;
for (int i=2;i<=n;i++)
if ((sa[i-1]<l && sa[i]>l) || (sa[i-1]>l && sa[i]<l))
ans=max(ans,height[i]);
printf("%d",ans);
return 0;
}
Solution
后缀自动机。
将一个串构成后缀自动机以后，另一个串在上面匹配就可以了，跳par的时候长度也要更新。
代码
// poj2774
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#define LL long long
#define inf 1<<30
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int maxn=100010;
int n;
char s[maxn];
namespace SAM {
int last,Dargen,sz;
int len[maxn<<1],ch[maxn<<1][26],par[maxn<<1];
void Extend(int c) {
int np=++sz,p=last;last=np;
len[np]=len[p]+1;
for (;p && !ch[p][c];p=par[p]) ch[p][c]=np;
if (!p) par[np]=Dargen;
else {
int q=ch[p][c];
if (len[q]==len[p]+1) par[np]=q;
else {
int nq=++sz;len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
par[nq]=par[q];
par[np]=par[q]=nq;
for (;p && ch[p][c]==q;p=par[p]) ch[p][c]=nq;
}
}
}
void build() {
Dargen=sz=last=1;
for (int i=1;i<=n;i++) Extend(s[i]-'a');
}
int query(char *s) {
int ans=0,ll=0;
int l=strlen(s+1);
for (int p=Dargen,i=1;i<=l;i++) {
while (p>1 && !ch[p][s[i]-'a']) p=par[p],ll=len[p];
if (ch[p][s[i]-'a']) {
p=ch[p][s[i]-'a'];
ll++;ans=max(ans,ll);
}
}
return ans;
}
}
using namespace SAM;
int main() {
scanf("%s",s+1);
n=strlen(s+1);
build();
scanf("%s",s+1);
printf("%d",query(s));
return 0;
}