[spoj LCS2] Longest Common Substring II

求多个字符串公共子串的最大长度. (字符集为小写英文字母, 串不多于10个, 每个长度不超过10^5) 先考虑怎样求两个字符串A,B的最长公共子串. 一个方法是, 将两者的后缀树分别建出来, 求它们的交. 有另一个常数更小的方法:

建出A的后缀自动机, 用它读入B, 以此求出每个状态所代表的子串 (一些前缀的长度连续的后缀) 与B的最大匹配长度. 设新读入字符c, 之前在状态x. 如果x有一个标号为c的转移, 就走过去; 否则, 沿着后缀链接向上跳, 直至到达一个有转移c的x', 或者已经跳到了初始状态. 这样均摊下来总时间是线性的: 向上跳的步数不多于len[x]的减少, 而len[x]每读入一个字符至多增加1, 且始终不小于0, 因此, len[x]的减少不多于|B|. 最后, 沿后缀链接把前面计算出的匹配长度向上更新一遍.

多个字符串并没有增加问题的难度. 对第一个串建后缀自动机. 对于状态s, 设第i个串与它所代表子串的最大匹配长度为ai, 则 min {ai} 是它们同时与s匹配的最大长度.

时间复杂度线性.

template<typename T>
inline void upmax(T& x, T v)
{
	x = max(x, v);
}

template<typename T>
inline void upmin(T& x, T v)
{
	x = min(x, v);
}

const int M = 10, N = 1e5, SIGMA = 26, inf = (1<<30)-1;

struct Node {
	Node* ch[SIGMA], * fa;
	int len, f, g;
	Node(): fa(0), len(0), f(0), g(inf)
	{
		fill_n(ch, SIGMA, (Node*)0);
	}
} node[2*N], * root = node, * seq[2*N];

int ptr = 1;

void add(int c)
{
	static Node* last = root;
	Node* p = last, * now = node + ptr++;
	last = now;
	now->len = p->len + 1;
	
	while (p && !p->ch[c]) {
		p->ch[c] = now;
		p = p->fa;
	}

	if (!p) {
		now->fa = root;
		return;
	}

	Node* q = p->ch[c];
	if (q->len == p->len + 1) {
		now->fa = q;
	} else {
		Node* nq = node + ptr++;
		*nq = *q;
		nq->len = p->len + 1;
		now->fa = q->fa = nq;
		while (p && p->ch[c] == q) {
			p->ch[c] = nq;
			p = p->fa;
		}
	}
}

void counting_sort(int n)
{
	static int cnt[N+1];
	rep (i, 0, ptr)
		++cnt[node[i].len];
	rep (i, 0, n)
		cnt[i+1] += cnt[i];
	rep (i, 0, ptr)
		seq[--cnt[node[i].len]] = node + i;
}

void match(char* s)
{
	Node* x = root;
	int l = 0;
	for (; *s; ++s) {
		int c = *s - 'a';
		if (x->ch[c]) {
			upmax((x = x->ch[c])->f, ++l);
			continue;
		}
		while (x && !x->ch[c]) x = x->fa;
		if (x) {
			l = x->len + 1;
			upmax((x = x->ch[c])->f, l);
		} else {
			l = 0;
			x = root;
		}
	}
}

void update()
{
	per (i, ptr-1, 1) {
		Node* x = seq[i];
		upmin(x->g, x->f);
		upmax(x->fa->f, min(x->f, x->fa->len));
		x->f = 0;
	}
}

char s[M][N+1];

int main()
{
	int m = 0, n = 0;
	while (scanf("%s", s[m]) == 1) ++m;
	while (s[0][n]) add(s[0][n++] - 'a');
	counting_sort(n);
	rep (i, 1, m) {
		match(s[i]);
		update();
	}
	int ans = 0;
	rep (i, 1, ptr) upmax(ans, node[i].g);
	printf("%d\n", ans);
	return 0;
}