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

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

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

#include <bits/stdc++.h>

using namespace std;
//#define map unordered_map
//#define int long long
const int N = 2.5e5 + 10, M = N << 1;
int fa[M], ch[M][26], len[M], cnt[M];
int np = 1, tot = 1;
char s[N];
int now[M];

void extend(int c) {
    
	int p = np;
	np = ++tot;
	len[np] = len[p] + 1, cnt[np] = 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()
{
    
	cin >> s;
	for (int i = 0; s[i]; ++i) {
    
		extend(s[i] - 'a');
	}
	cin >> s;
	int p = 1, t = 0;
	for (int i = 0; s[i]; ++i) {
    
		int c = s[i] - 'a';
		while (p > 1 && !ch[p][c]) {
    
			p = fa[p];
			t = len[p];
		}
		if (ch[p][c]) p = ch[p][c], ++t;
		now[p] = max(now[p], t);
	}

	int res = -1;
	for (int i = 1; i <= tot; ++i) {
    
		res = max(res, now[i]);
	}
	cout << res << '\n';

	return 0;
}