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 a bit harder, for some 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 at most 10 lines, each line consists of no more than 100000 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
aaaajfaaaa

Output:
2

Notice: new testcases added

两个月前留下的万年老坑终于填了……

题目大意很简单，求10个串的最长公共子串，长度范围1e5。

由于数据范围比较容易想到后缀自动机。我们可以先对第一个字符串建立一个后缀自动机，用后面的每一个串跑。记录下每一个节点的最大匹配长度mx[i]。每一次跑完过后更新对于所有串跑出来每一个节点mx结果的最小值mn。最后在所有点的mn值中选取最大的即可。

需要注意的是，因为儿子节点的更新会让父亲节点的值改变，所以跑完一遍后缀自动机要按拓扑序向上更新父亲的mx值。而求一个后缀自动机的拓扑序很简单，就是所有节点按len值排序就行了（后缀自动机的性质）。所以我们可以基数排序一遍，得到拓扑序。渣渣常数的代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 20;
int trie[maxn][26], len[maxn], fa[maxn], dp[maxn], tdp[maxn], num[maxn], last, cnt, top[maxn];
char s[maxn], ms[maxn];

void add(int x) {
	int id = s[x] - 'a';
	int np = ++cnt, p = last;
	last = np;
	len[np] = tdp[np] = x + 1;
	while(p && !trie[p][id]) {
		trie[p][id] = np;
		p = fa[p];
	}
	if(p == 0) fa[np] = 1;
	else {
		int q = trie[p][id];
		if(len[p] + 1 == len[q]) fa[np] = q;
		else {
			int lca = ++cnt;
			len[lca] = tdp[lca] = len[p] + 1;
			fa[lca] = fa[q];
			fa[q] = fa[np] = lca;
			memcpy(trie[lca], trie[q], sizeof(trie[q]));
			while(p && trie[p][id] == q) {
				trie[p][id] = lca;
				p = fa[p];
			}
		}
	}
}

void work() {
	int p = 1, step = 0;
	int l = strlen(ms);
	for(register int i = 0; i < l; ++i) {
		int id = ms[i] - 'a';
		if(trie[p][id]) ++step, p = trie[p][id];
		else {
			while(p && !trie[p][id]) p = fa[p];
			if(!p) p = 1, step = 0;
			else step = len[p] + 1, p = trie[p][id];
		}
		if(dp[p] < step) dp[p] = step;
	}
	for(register int i = cnt; i; --i) {
		p = top[i];
        if(dp[p] < tdp[p]) tdp[p] = dp[p];
        if(fa[p] && dp[fa[p]] < dp[p]) dp[fa[p]] = dp[p];
        dp[p]=0;
	}
}

int main() {
	last = cnt = 1;
	int mx = 0;
	scanf("%s", s);
	int l = strlen(s);
	for(register int i = 0; i < l; ++i) add(i);
	for(register int i = 1; i <= cnt; ++i) ++num[len[i]];
	for(register int i = 1; i <= l; ++i) num[i] += num[i - 1];
	for(register int i = 1; i <= cnt; ++i) top[num[len[i]]--] = i;
	while(~scanf("%s", ms)) work();
	for(register int i = 1; i <= cnt; ++i)
		if(mx < tdp[i]) mx = tdp[i];
	printf("%d", mx);
	return 0;
}