CODE【VS】3160 最长公共子串（后缀自动机）

3160 最长公共子串

题目描述 Description

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

输入描述 Input Description

读入两个字符串

输出描述 Output Description

输出最长公共子串的长度

样例输入(Sample Input)

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit

yeaphowmuchiloveyoumydearmother

样例输出(Sample Output)

27

数据范围及提示

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

后缀自动机模版题，先以第一个串建立一个后缀自动机，第二个串直接匹配

#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=100005;

const int sigma=27;

int n;

char ch[N<<1];

struct sam{

	int cnt,last;

	int fa[N<<1],a[N<<1][sigma],mx[N<<1],len[N<<1];

	sam(){

		last=++cnt;

	}

	void extend(int c){

		int p=last,np=last=++cnt;mx[np]=mx[p]+1;

		while(!a[p][c]&&p)a[p][c]=np,p=fa[p];

		if(!p)fa[np]=1;

		else

		{

			int q=a[p][c];

			if(mx[p]+1==mx[q])fa[np]=q;

			else

			{

				int nq=++cnt;mx[nq]=mx[p]+1;

				memcpy(a[nq],a[q],sizeof(a[q]));

				fa[nq]=fa[q];

				fa[np]=fa[q]=nq;

				while(a[p][c]==q)a[p][c]=nq,p=fa[p];

			}

		}

	}

	void solve(){

		scanf("%s",ch+1);

		memset(len,0,sizeof(len));

		int l=strlen(ch+1),p=1,tmp=0,ans=0;

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

		{

			int c=ch[i]-'a';

			while(!a[p][c]&&p)p=fa[p];

			if(p==0)p=1,tmp=0;

			else tmp=min(tmp,mx[p])+1,p=a[p][c];

			ans=max(ans,tmp);

		}

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

	}

}sam;

int main()

{

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

    {

	    int n=strlen(ch+1);

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

	    sam.solve();

    }

    return 0;

}

巴特西

CODE【VS】3160 最长公共子串（后缀自动机）

3160 最长公共子串

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入(Sample Input)

样例输出(Sample Output)

数据范围及提示

最新文章

热门文章

巴特西

CODE【VS】3160 最长公共子串 （后缀自动机）

3160 最长公共子串

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入(Sample Input)

样例输出(Sample Output)

数据范围及提示

最新文章

热门文章

CODE【VS】3160 最长公共子串（后缀自动机）