LCS2 - Longest Common Substring II
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
求若干个字符串的最长公共子串。
显然，如果是所有字符串的最长公共子串，至少得是第一个字符串的一个子串，所以对第一个字符串建后缀自动机，维护所有子串。然后把每个其他的字符串扔进去跑一边，找出来最远的公共点即可。
#include <bits/stdc++.h> const int maxn = 1e6 + ; /* AUTOMATON */ int last;
int tail;
int mini[maxn];
int maxi[maxn];
int step[maxn];
int fail[maxn];
int next[maxn][]; inline void buildAutomaton(char *s)
{
last = ; tail = ;
while (*s)
{
int c = *s++ - 'a';
int p = last;
int t = tail++;
step[t] = step[p] + ;
mini[t] = maxi[t] = step[t];
while (p && !next[p][c])
next[p][c] = t, p = fail[p];
if (p)
{
int q = next[p][c];
if (step[q] == step[p] + )
fail[t] = q;
else
{
int k = tail++;
fail[k] = fail[q];
fail[q] = fail[t] = k;
step[k] = step[p] + ;
mini[k] = maxi[k] = step[k];
memcpy(next[k], next[q], sizeof(next[k]));
while (p && next[p][c] == q)
next[p][c] = k, p = fail[p];
}
}
else
fail[t] = ;
last = t;
}
} inline void searchAutoMaton(char *s)
{
memset(maxi, , sizeof(maxi));
for (int t = , k = ; *s; )
{
int c = *s++ - 'a';
if (next[t][c])
++k, t = next[t][c];
else
{
while (t && !next[t][c])
t = fail[t];
if (t)
k = step[t] + , t = next[t][c];
else
k = , t = ;
}
if (maxi[t] < k)
maxi[t] = k;
}
for (int i = tail - ; i; --i)
if (maxi[fail[i]] < maxi[i])
maxi[fail[i]] = maxi[i];
for (int i = ; i < tail; ++i)
if (mini[i] > maxi[i])
mini[i] = maxi[i];
} inline int calculate(void)
{
register int ret = ;
for (int i = ; i < tail; ++i)
if (ret < mini[i])
ret = mini[i];
return ret;
} /* MAIN FUNC */ char str[maxn]; signed main(void)
{
scanf("%s", str);
buildAutomaton(str);
while (~scanf("%s", str))
searchAutoMaton(str);
printf("%d\n", calculate());
}
@Author: YouSiki