Why did I RE?
查看原帖
Why did I RE?
573963
wbh20090611楼主2024/11/7 20:35

rt

#include <bits/stdc++.h>
using namespace std;
const int N = 200006, M = 206, K = 16;
vector <int> f[N];
char s1[N], s2[M][K];
int p[K], l1, l2[M], n, ans;
bool dp[N];
int KMP(char s2[], int l2)
{
	p[1] = 0;
	for (int i = 2, j = 0; i <= l2; i++)
	{
		while (j > 0 && s2[i] != s2[j + 1])
			j = p[j];
		if (s2[i] == s2[j + 1])
			j++;
		p[i] = j;
	}
	for (int i = 1, j = 0; i <= l1; i++)
	{
		while (j > 0 && s1[i] != s2[j + 1])
			j = p[j];
		if (s1[i] == s2[j + 1])
			j++;
		if (j == l2)
		{
			f[i - l2 + 1].push_back(l2);
			j = p[j];
		}
	}
}
int main()
{
	while(scanf("%s", s2[++n] + 1) != EOF)
	{
		if (s2[n][1] == '.')
			break;
		l2[n] = strlen(s2[n] + 1);
	}
	scanf("%s", s1 + 1);
	l1 = strlen(s1 + 1);
	for (int i = 1; i <= n; i++)
		KMP(s2[i], l2[i]);
	dp[1] = true;
	for (int i = 1; i <= l1; i++)
	{
		if (dp[i])
			for (auto j : f[i])
			{
				dp[i + j] = true;
				ans = max(ans, i + j - 1);
			}
	}
	cout << ans;
}
2024/11/7 20:35
加载中...