【POJ2774】Long Long Message-求最长公共子串（后缀数组求法）

题目大意：求两个字符串（长度≤100000）的最长公共子串长度。

做法：这里用后缀数组来求。求法是将两个字符串拼成一个字符串，中间加一个其他的字符，对这个字符串求一遍后缀数组，然后找height数组中的最大值。注意，只有当排在一起的两个后缀不属于同一个字符串时，才计入最大值的计算。

以下是本人代码（模板写的很丑...用的是倍增算法求后缀数组，凑合看吧）：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
char s[200010],b[100010];
int SA[200010],rank[200010],height[200010],len,lenf;
int x[400010]={0},y[400010]={0},cnt[200010]={0},ws[400010],wv[400010];
int ans=0;

void calc_SA() //对字符串s求后缀数组
{
  for(int i=0;i<len;i++) x[i]=s[i]-'a'+1;
  int p=1,m=27;
  while(p<len)
  {
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<len;i++) {y[i]=x[i+p];cnt[y[i]]++;}
	for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
	for(int i=m;i>=1;i--) cnt[i]=cnt[i-1];
	cnt[0]=0;
	for(int i=0;i<len;i++) ws[cnt[y[i]]++]=i;
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<len;i++) cnt[x[i]]++;
	for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
	for(int i=m;i>=1;i--) cnt[i]=cnt[i-1];
	cnt[0]=0;
	for(int i=0;i<len;i++) wv[cnt[x[ws[i]]]++]=ws[i];
	ws[wv[0]]=1;
	for(int i=1;i<len;i++)
	{
	  if (x[wv[i]]==x[wv[i-1]]&&y[wv[i]]==y[wv[i-1]]) ws[wv[i]]=ws[wv[i-1]];
	  else ws[wv[i]]=ws[wv[i-1]]+1;
	}
	m=0;
	for(int i=0;i<len;i++) {x[i]=ws[i];m=std::max(m,x[i]);}
	p=p<<1;
  }
  for(int i=1;i<=len;i++) rank[i]=x[i-1];
  for(int i=1;i<=len;i++) SA[rank[i]]=i;
}

void calc_height() //求height数组
{
  int j,k=0;
  for(int i=1;i<=len;height[rank[i++]]=k)
    for(k?k--:0,j=SA[rank[i]-1]-1;s[i+k-1]==s[j+k];k++);
}

int main()
{
  scanf("%s%s",s,b);
  lenf=strlen(s);
  s[strlen(s)]='{';
  int lenb=strlen(b);
  for(int i=strlen(s),j=0;j<lenb;j++) //切记不要直接在for循环的比较中直接调用strlen，先把长度记下来会省去很多调用函数的时间
    s[i+j]=b[j];
  len=strlen(s);
  
  calc_SA();
  calc_height();

  for(int i=1;i<len;i++)
  {
    if ((SA[i]<lenf+1&&SA[i+1]>lenf+1)||(SA[i+1]<lenf+1&&SA[i]>lenf+1))
	  ans=std::max(height[i+1],ans);
  }
  
  printf("%d",ans);
  
  return 0;
}

【POJ2774】Long Long Message-求最长公共子串（后缀数组求法）

相关推荐