Rockdu's Blog

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is simple, for two given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn't exist, print "0" instead.

Example

Input:
alsdfkjfjkdsal
fdjskalajfkdsla

Output:
3

Notice: new testcases added

后缀自动机加一个小小的最值处理，对两个串就可以完美解决了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=250100;
char s[maxn];
int trie[maxn*2][26],fail[maxn*2],len[maxn*2];
int mx[maxn*2],mn[maxn*2];
int cnt,last,strl;//根节点为1 

void add(int x)
{
	int id=s[x]-'a';
	int np=++cnt,p=last;
	last=np;
	len[np]=x+1;
	while(p && !trie[p][id])
	{
		trie[p][id]=np;
		p=fail[p];
	}
	if(p==0)
		fail[np]=1;  //fail指针设到根节点
	else
	{
		int q=trie[p][id];
		if(len[p]+1==len[q])
			fail[np]=q;
		else
		{
			int lca=++cnt;
			len[lca]=len[p]+1;
			fail[lca]=fail[q];
			fail[q]=fail[np]=lca;
			memcpy(trie[lca],trie[q],sizeof(trie[q]));
			while(p && trie[p][id]==q)
				{
					trie[p][id]=lca;
					p=fail[p];
				}
		}
	} 
	
}

int work()
{
	int length=strlen(s);
	int ans=0;
	int l=0;
	int now=1;
	for(int i=0;i<length;i++)
	{
		int id=s[i]-'a';
		if(trie[now][id])
		{
			l++;
			now=trie[now][id];
		}
		else
		{
			while(now!=0 && !trie[now][id])
				now=fail[now];
			if(now==0)
				now=1,l=0;
			else	l=len[now]+1,now=trie[now][id];
		}
		ans=max(ans,l);
	}
	return ans;
}

int main()
{
	cnt=last=1;
	scanf("%s",s);
	strl=strlen(s);
	for(int i=0;i<strl;i++)
			add(i);
	int nct=0x3f3f3f3f,j=0;
	while(scanf("%s",s)!=EOF)
	{
		nct=work();
		if(++j==1)
		break;
	}
	printf("%d\n",nct);
	return 0;
}