CODE【VS】 3160 最长公共子串 (后缀数组)

3160 最长公共子串

题目描述 Description

给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。

输入描述 Input Description

读入两个字符串

输出描述 Output Description

输出最长公共子串的长度

样例输入(Sample Input)

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit

yeaphowmuchiloveyoumydearmother

样例输出(Sample Output)

27

数据范围及提示

单个字符串的长度不超过100000

将两个串链接成一个串，之后直接求hight数组即可，同时要求：

两个后缀只来自各自的字符串

这一点只要在中间加个特殊字符即可，因为只要使得两个后缀的起始点来自于不同串，特殊字符会使得他们在求lcp时断开

/*

作者:Acforgood

题目:p3160 最长公共子串

*/

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 300

#define mod 1000000007

using namespace std;

int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int N=200005;

int n;

char ch[N];

int a[N],h[N];

int v[N];

int sa[2][N],rk[2][N];

int p,q,k;

void calsa(int sa[N],int rk[N],int SA[N],int RK[N])

{

    for(int i=1; i<=n; i++)v[rk[sa[i]]]=i;

    for(int i=n; i; i--)

        if(sa[i]>k)

            SA[v[rk[sa[i]-k]]--]=sa[i]-k;

    for(int i=n-k+1; i<=n; i++)SA[v[rk[i]]--]=i;

    for(int i=1; i<=n; i++)

        RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);

}

void work()

{

    p=0,q=1;

    for(int i=1; i<=n; i++)v[a[i]]++;

    for(int i=1; i<=30; i++)v[i]+=v[i-1];

    for(int i=1; i<=n; i++)

        sa[p][v[a[i]]--]=i;

    for(int i=1; i<=n; i++)

        rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);

    for(k=1; k<n; k<<=1)

    {

        calsa(sa[p],rk[p],sa[q],rk[q]);

        swap(p,q);

    }

}

void geth()

{

    k=0;

    for(int i=1; i<=n; i++)

        if(rk[p][i]==1)h[rk[p][i]]=0;

        else

        {

            int j=sa[p][rk[p][i]-1];

            while(a[i+k]==a[j+k])k++;

            h[rk[p][i]]=k;

            if(k>0)k--;

        }

}

int main()

{

    while(~scanf("%s",ch+1))

    {

        n=strlen(ch+1);

        int len=n+1;

        ch[n+1]='a'-1;

        scanf("%s",ch+n+2);

        n=strlen(ch+1);

        for(int i=1; i<=n; i++)a[i]=ch[i]-'a'+1;

        work();

        geth();

        int ans=0;

        for(int i=1; i<=n; i++)

        {

            if((sa[p][i]>len&&sa[p][i-1]<len)||(sa[p][i]<len&&sa[p][i-1]>len)) ans=max(ans,h[i]);

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

CODE【VS】 3160 最长公共子串 (后缀数组)

3160 最长公共子串

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入(Sample Input)

样例输出(Sample Output)

数据范围及提示

最新文章

热门文章