题目大意:给两个DNA序列,求这两个序列的最长公共子串,按字典序输出,长度N<=300
可以直接用O(n^3)的暴力过。用后缀数组时间复杂度为O(nlogn)。。
先遍历height数组求出最大长度,然后再扫一遍height数组,记录最长子串的起始位置。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<vector>
using namespace std;
int sa[710],r[710],h[710],c[710],x[710],y[710],bel[710]; //bel数组记录当前字符原本属于哪个字符串
char s[710],t[710];
set<int>se;
vector<int>g;
void build(int n,int m){
int i,j,k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++){
x[i]=s[i]-'a'+1;
c[x[i]]++;
}
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(j=1;j<n;j*=2){
k=0;
for(i=n-j;i<n;i++) y[k++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[k++]=sa[i]-j;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
m=0;
x[sa[0]]=m++;
for(i=1;i<n;i++){
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]) x[sa[i]]=m-1;
else x[sa[i]]=m++;
}
if(m>=n) break;
}
k=0;
for(i=0;i<n;i++) r[sa[i]]=i;
for(i=0;i<n-1;i++){
j=sa[r[i]-1];
if(k) k--;
while(s[i+k]==s[j+k]) k++;
h[r[i]]=k;
}
}
int main(){
int i,j,n,m,a,ca=0;
while(scanf("%s%s",&s,&t)!=EOF){
if(ca) printf("\n");
ca++;
memset(bel,0,sizeof(bel));
g.clear();
se.clear();
n=strlen(s);
m=strlen(t);
for(i=0;i<n;i++) bel[i]=1; //拼接两个字符串
s[n++]='z'+1;
for(i=0;i<m;i++){
bel[n]=2;
s[n++]=t[i];
}
s[n++]='a'-1;
build(n,30);
int ma=0,a;
for(i=1;i<n;i++) if(bel[sa[i]]+bel[sa[i-1]]==3&&h[i]>ma) ma=h[i]; //求最大长度
if(ma==0){
printf("No common sequence.\n");
continue;
}
for(i=1;i<n;i++){ //按字典序记录不同的最长子串起始位置
if(h[i]>=ma){
a=sa[i];
se.insert(bel[sa[i]]);
se.insert(bel[sa[i-1]]);
}
else{
if(se.size()==2) g.push_back(a);
se.clear();
}
}
for(i=0;i<g.size();i++){
a=g[i];
for(j=a;j<a+ma;j++) printf("%c",s[j]);
printf("\n");
}
}
return 0;
}