Ural 1517 最长公共子序列

Sample Input

28
VOTEFORTHEGREATALBANIAFORYOU
CHOOSETHEGREATALBANIANFUTURE

THEGREATALBANIA

题意：求最长公共子序列，要求输出，

遇上一题一样，加一点记录就行。

代码：

/* ***********************************************
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("%d",&m))
      {
	     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);
	     // printf("sa:");for(i=0;i<=len;i++)printf("%d ",sa[i]);puts("");
       //	printf("rank:");for(i=0;i<=len;i++)printf("%d ",rank[i]);puts("");
       //	printf("height:");for(i=0;i<=len;i++)printf("%d ",height[i]);puts("");
	     int be,ans=0;
	     for(i=1;i<=len;i++)
	     {
		    if((sa[i]<l1&&sa[i-1]>l1)||(sa[i]>l1&&sa[i-1]<l1))
		    if(ans<height[i])ans=height[i],be=sa[i];
	     }
	     for(i=be;i<be+ans;i++)putchar(str[i]);
	     puts("");
      }
      return 0;
}

Ural 1517 最长公共子序列

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