最长公共子串

一：动态规划
http://blog.csdn.net/w305172521/article/details/50461200
https://www.rqnoj.cn/problem/164

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
char s[100010];
char str[100010];
int len,length,maxl;
int num[2][100010];
int longest_Common_Substring()//求长度
{
    maxl=0;
    int w=0;
    memset(num,0,sizeof(num));
    len=strlen(s);
    length=strlen(str);
    for(int i=1;i<len+1;i++)
    {

        for(int j=1;j<length+1;j++)
        {
            if(s[i-1]==str[j-1])
            {
                num[w][j]=num[w^1][j-1]+1;
            }
            else num[w][j]=0;
            maxl=maxl<num[w][j]?num[w][j]:maxl;
        }
        w^=1;
    }
    return maxl;
}
string LCS()//求子串
{
    string tmp="";
    string substring[2][100010];
    int w=0;
    maxl=0;
    len=strlen(s);
    length=strlen(str);
    for(int i=1;i<len+1;i++)
    {

        for(int j=1;j<length+1;j++)
        {
            if(s[i-1]==str[j-1])
            {
                substring[w][j]=substring[w^1][j-1]+s[i-1];
            }
            else substring[w][j]="";
            if(substring[w][j].length()>maxl)
            {
                tmp=substring[w][j];
                maxl=substring[w][j].length();
            }
        }
        w^=1;
    }
    return tmp;
}
int main()
{

    scanf("%s%s",s,str);
    cout<<LCS()<<endl;
     printf("%d\n",longest_Common_Substring());
    return 0;
}

二:后缀数组

字符串的任何一个子串都是这个字符串的某个后缀的前缀。求 A 和 B 的最长
公共子串等价于求 A 的后缀和 B 的后缀的最长公共前缀的最大值。如果枚举 A
和 B 的所有的后缀,那么这样做显然效率低下。由于要计算 A 的后缀和 B 的后缀
的最长公共前缀,所以先将第二个字符串写在第一个字符串后面,中间用一个没
有出现过的字符隔开,再求这个新的字符串的后缀数组。那么是不是所有的 height 值中的最大值就是答案呢?不一定!有可能这两个 后 缀 是 在 同 一 个 字 符 串 中 的 , 所 以 实 际 上 只 有 当 suffix(sa[i-1]) 和suffix(sa[i])不是同一个字符串中的两个后缀时,height[i]才是满足条件的。而这其中的最大值就是答案。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 200010
using namespace std;
char s[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn],Rank[maxn],height[maxn],n,n1;
void build_sa(int m){
    int i,*x=t,*y=t2,*T,p ;
    n++;
    for(i=0;i<m;++i)c[i]=0;
    for(i=0;i<n;++i)++c[x[i]=s[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(int k=1;k<=n;k<<=1)
    {
          p=0;
       for(i=n-1;i>=n-k;--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);
       x[sa[0]]=0;p=1;
       for(i=1;i<n;++i)
         x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
       if(p>=n)break;
       m=p;
    }
    n--;
   // for(int i=1;i<=n;++i)printf("%d ",sa[i]+1);
   // printf("\n");

}
void cal_height(){
    int i,j,k=0;
    for(i=1;i<=n;i++)Rank[sa[i]]=i;
    for(int i=0;i<n;++i)
    {
       j=sa[Rank[i]-1];//h[i-1]
       if(k)k--;
       while(s[i+k]==s[j+k])k++;
       height[Rank[i]]=k;//h[i]
    }
    //for(int i=2;i<=n;++i)printf("%d ",height[i]);
}
int main(){
    while(scanf("%s",s)!=EOF)
    {
        n1=strlen(s);
        s[n1]='A';
        scanf("%s",s+n1+1);
        n=strlen(s);
        build_sa(255);
        cal_height();
        int maxl=0;
        for(int i=2;i<=n;i++)
        {
            if(maxl<height[i])
            {
                if((sa[i]<n1&&sa[i-1]>n1)||(sa[i]>n1&&sa[i-1]<n1))
                maxl=height[i];
            }
        }
        printf("%d\n",maxl);
    }
}