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;

}