SPOJ 2774 Longest Common Substring（两串求公共子串 SAM）

有了之前提到过的 多串最长公共子串，当然也要有 两串求公共子串

两者都可用 SAM 求解，具体解法可见 AcWing 2811. 多串最长公共子串（后缀自动机 fa 指针的性质）

#include<bits/stdc++.h>

using namespace std;
const int N = 2.5e5 + 10, M = N << 1;
char s[N], q[N];
int ch[M][26], len[M], fa[M], tot = 1, np = 1, ans[M];

void extend(int c)
{
	int p = np; np = ++tot;
	len[np] = len[p] + 1;
	while (p && !ch[p][c]) {
		ch[p][c] = np;
		p = fa[p];
	}
	if (!p) {
		fa[np] = 1;
	}
	else {
		int q = ch[p][c];
		if (len[q] == len[p] + 1) {
			fa[np] = q;
		}
		else {
			int nq = ++tot;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q], fa[q] = fa[np] = nq;
			while (p && ch[p][c] == q) {
				ch[p][c] = nq;
				p = fa[p];
			}
			memcpy(ch[nq], ch[q], sizeof ch[q]);
		}
	}
}

signed main()
{
	scanf("%s", s);
	for (auto ch : s) {
		extend(ch - 'a');
	}
	scanf("%s", q);
	int t = 0, p = 1;
	for (int i = 0; q[i]; ++i) {
		int c = q[i] - 'a';
		while (p > 1 && !ch[p][c]) {
			p = fa[p];
			t = len[p];
		}
		if (ch[p][c]) ++t, p = ch[p][c];
		ans[p] = max(ans[p], t);
	}
	int res = -1;
	for (int i = 1; i <= tot; ++i) {
		res = max(res, ans[i]);
	}
	printf("%d\n", res);

	return 0;
}