POJ 2774 两个字符串的最长公共子序列。

Description

Input

Output

Sample Input

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother

Sample Output

27
题意：给定两个序列，求最长公共子序列的长度。
解题思路：将两个串连起来，在中间加一个未出现过的字符分割，然后枚举相邻sa的height值，假如他们属于不同的序列，则更新取最大值。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-1-28 18:11:33
File Name :4.cpp
************************************************ */

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=2000200;
int height[maxn],sa[maxn],rank[maxn],c[maxn],t1[maxn],t2[maxn];
void da(int *str,int n,int m)
{
      int i,j,k,p,*x=t1,*y=t2;
      for(i=0;i<m;i++)c[i]=0;
      for(i=0;i<n;i++)c[x[i]=str[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(k=1;k<=n;k<<=1)
      {
	     p=0;
	     for(i=n-k;i<n;i++)y[p++]=i;
	     for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
	     for(i=0;i<m;i++)c[i]=0;
	     for(i=0;i<n;i++)c[x[y[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);
	     p=1;x[sa[0]]=0;
	     for(i=1;i<n;i++)
	     x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
	     if(p>=n)break;
	     m=p;
      }
}
void calheight(int *str,int n)
{
      int i,j,k=0;
      for(i=0;i<=n;i++)rank[sa[i]]=i;
      for(i=0;i<n;i++)
      {
	     if(k)k--;
	     j=sa[rank[i]-1];
	     while(str[i+k]==str[j+k])k++;
	     height[rank[i]]=k;
      }
}
int str[maxn];
char ss[maxn];
int Log[maxn];
int best[23][maxn];
void init(int n)
{
      int i,j;
      Log[0]=-1;
      for(i=1;i<=n;i++)
	     Log[i]=(i&(i-1))?Log[i-1]:Log[i-1]+1;
      for(i=1;i<=n;i++)best[0][i]=height[i];
      for(i=1;i<=Log[n];i++)
	     for(j=1;j<=n;j++)
		    best[i][j]=min(best[i-1][j],best[i-1][j+(1<<(i-1))]);
}
int lcp(int a,int b)
{
      a=rank[a];
      b=rank[b];
      if(a>b)swap(a,b);
      a++;
      int t=Log[b-a+1];
      return min(best[t][a],best[t][b-(1<<t)+1]);
}
char s1[maxn],s2[maxn];
int main()
{
      //freopen("data.in","r",stdin);
      //freopen("data.out","w",stdout);
      int i,j,k,m,n;
      while(~scanf("%s%s",s1,s2))
      {
	     int l1=strlen(s1);
	     int l2=strlen(s2);
	     int len=0;
	     for(i=0;i<l1;i++)str[len++]=s1[i];
	     str[len++]=1;
	     for(i=0;i<l2;i++)str[len++]=s2[i];
	     str[len]=0;
	     da(str,len+1,300);
	     calheight(str,len);

	     int ans=0;
	     for(i=2;i<len;i++)
	     {
		    if((sa[i]<l1&&sa[i-1]>l1)||(sa[i]>l1&&sa[i-1]<l1))
			   ans=max(ans,height[i]);
	     }
	     printf("%d\n",ans);
      }
      return 0;
}

POJ 2774 两个字符串的最长公共子序列。

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18845869