USACO2.3 最长前缀 Longest Prefix

传送门

逐个对集合 $P$ 中的字符串进行 KMP ，得出其在串 $S$ 中的所有覆盖区间。问题转换成如何选取相互无重合部分的区间，以 $S$ 串的左端点为起点，能覆盖最大的连续区域。

对区间以左端点为关键字，从小到大进行排序。定义数组 $b_i$ 记录点 $i$ 的左侧是否已被全部无重合地覆盖。枚举区间，若区间左端点的左边已全部覆盖，即 $b_l = 1$，则该区间可选取，使 $b_{r+1} = 1$。同时更新答案 $ans = r$。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2000010; 

string t[N], s, str;
int nxt[N], cnt, b[N], tot, ans = -1;
struct Node {
	int l, r;
	friend bool operator < (const Node &a, const Node &b) {
		return a.l < b.l;
	}
} a[N];

int main()
{
	freopen("c.txt", "r", stdin);
	while (1) {
		cin >> str;
		if (str == ".") break;
		t[++tot] = str;
	}
	while (cin >> str) {
		s = s + str;
	}
	for (int i = 1; i <= tot; i++) {
		memset(nxt, 0, sizeof(nxt));
		for (int j = 1, k = 0; j < t[i].size(); j++) {
			while (k > 0 && t[i][k] != t[i][j])
				k = nxt[k - 1];
			if (t[i][k] == t[i][j]) ++k;
			nxt[j] = k;
		}
		for (int j = 0, k = 0; j < s.size(); j++) {
			while (k > 0 && s[j] != t[i][k])
				k = nxt[k - 1];
			if (s[j] == t[i][k]) k++;
			if (k == t[i].size()) {
				a[++cnt] = (Node){j - t[i].size() + 1, j};
				k = nxt[k - 1];
			}
		}
	}
	sort(a + 1, a + 1 + cnt);
	b[0] = 1;
	for (int i = 1; i <= cnt; i++) {
		if (!b[a[i].l]) continue;
		b[a[i].r + 1] = 1;
		ans = max(ans, a[i].r);
	}
	printf("%d", ans + 1);
	return 0;
}