【SP1812】LCS2 - Longest Common Substring II

时间：2023-03-08 16:29:33
【SP1812】LCS2 - Longest Common Substring II

【SP1812】LCS2 - Longest Common Substring II

题面

洛谷

题解

你首先得会做这题。

然后就其实就很简单了，

你在每一个状态\(i\)打一个标记\(f[i]\)表示状态\(i\)能匹配到最长的子串长度，

显然\(f[i]\)可以上传给\(f[i.fa]\)。

然后去每个串和第\(1\)个串\(f\)的最小值的最大值即可。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int MAX_N = 1e5 + 5;

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

int tot = 1, lst = 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].len = t[p].len + 1, t[q].fa = t[tot - 1].fa = _q;

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

}

char a[MAX_N];

int N, A[MAX_N << 1], f[MAX_N << 1], g[MAX_N << 1], bln[MAX_N << 1];

int main () {

#ifndef ONLINE_JUDGE

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

#endif

	scanf("%s", a + 1);

	N = strlen(a + 1);

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

	for (int i = 1; i <= tot; i++) ++bln[t[i].len];

	for (int i = 1; i <= tot; i++) bln[i] += bln[i - 1];

	for (int i = 1; i <= tot; i++) A[bln[t[i].len]--] = i;

	for (int i = 1; i <= tot; i++) g[i] = t[i].len;

	while (scanf("%s", a + 1) != EOF) {

		N = strlen(a + 1);

		for (int i = 1; i <= tot; i++) f[i] = 0;

		for (int v = 1, l = 0, i = 1; i <= N; i++) {

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

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

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

			f[v] = max(f[v], l);

		}

		for (int i = tot; i; i--) f[t[i].fa] = max(f[t[i].fa], f[i]);

		for (int i = 1; i <= tot; i++) g[i] = min(g[i], f[i]);

	}

	printf("%d\n", *max_element(&g[1], &g[tot + 1]));

    return 0;

}

相关文章