BZOJ3620（kmp）

要点

本题使用\(O(n^2)\)的算法
外层枚举左端点，内层一直kmp到结尾，中间遇到合法的就ans++
如果是acccca这种数据直接kmp过程顺手判断即可；但是aaa这种数据，j = 2，实际判断是不合法的，也就是说，其实只要Next里有合法的即本串合法，因此多开Num数组记录

#include <cstdio>

#include <cstring>

#define min(a, b) a > b ? b : a

const int maxn = 15e3 + 5, INF = 0x3f3f3f3f;

int k, Next[maxn], Num[maxn], ans;

char str[maxn];

int main() {

	scanf("%s %d", str + 1, &k);

	int n = strlen(str + 1);

	for (int l = 1; l <= n; l++) {

		memset(Num, 0x3f, sizeof Num);

		Next[1] = 0;

		for (int len = 2, j = 0; len <= n - l + 1; len++) {

			int r = l + len - 1;

			while (j && str[r] != str[l + j])	j = Next[j];

			if (str[r] == str[l + j])	j++;

			Next[len] = j;

			if (j < k)	Num[len] = INF;

			else	Num[len] = min(Num[Next[len]], j);

			if (Num[len] * 2 < len)	ans++;

		}

	}

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

	return 0;

}

巴特西

BZOJ3620（kmp）

要点

最新文章

热门文章