【SP1811】LCS - Longest Common Substring

时间：2023-03-09 07:05:09
【SP1811】LCS - Longest Common Substring

【SP1811】LCS - Longest Common Substring

题面

洛谷

题解

建好后缀自动机后从初始状态沿着现在的边匹配，

如果失配则跳它的后缀链接，因为你跳后缀链接到达的\(Endpos\)集合中的串肯定是当前\(Endpos\)中的后缀，所以这么做是对的。

你感性理解一下，这样显然是最大的是吧。。。

具体实现看代码：

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int MAX_N = 2.5e5 + 5;

struct Node { int ch[26], fa, len; } t[MAX_N << 1];

int lst = 1, tot = 1;

void extend(int c) {

	++tot, t[lst].ch[c] = tot;

	t[tot].len = t[lst].len + 1;

	int p = t[lst].fa; lst = tot;

	while (p && !t[p].ch[c]) t[p].ch[c] = tot, p = t[p].fa;

	if (!p) return (void)(t[tot].fa = 1);

	int q = t[p].ch[c];

	if (t[q].len == t[p].len + 1) return (void)(t[tot].fa = q);

	int _q = ++tot;

	t[_q] = t[q], t[q].fa = t[tot - 1].fa = _q;

	t[_q].len = t[p].len + 1;

	while (p && t[p].ch[c] == q) t[p].ch[c] = _q, p = t[p].fa;

}

char s1[MAX_N], s2[MAX_N];

int N;

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	scanf("%s%s", s1 + 1, s2 + 1);

	N = strlen(s1 + 1);

	for (int i = 1; i <= N; i++) extend(s1[i] - 'a');

	N = strlen(s2 + 1);

	int ans = 0, l = 0, v = 1;

	for (int i = 1; i <= N; i++) {

		while (v && !t[v].ch[s2[i] - 'a']) v = t[v].fa, l = t[v].len;

		if (!v) v = 1, l = 0;

		if (t[v].ch[s2[i] - 'a']) v = t[v].ch[s2[i] - 'a'], ++l;

		ans = max(ans, l);

	}

	printf("%d\n", ans);

    return 0;

}

相关文章