43pts求调
查看原帖
43pts求调
470769
DengStar楼主2023/10/17 18:25

RT,写的是 exKMP 模板,但是把题目中的两个要求写在同一个函数里了,怀疑是这里出了问题。
提交后发现 WA 的测试点都是错在第二行,还有两个点 T 了,实在不知道为什么,有无大佬帮忙调一下?

// P5410 【模板】扩展 KMP/exKMP(Z 函数)
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN = 2e7 + 10;
int z[MAXN]; ll ans;
char a[MAXN], b[MAXN];

void getz(char *s, char *s1) // s 是文本,s1 是模式串 
{
	int len = strlen(s + 1), len1 = strlen(s1 + 1), L = 1, R = 1;
	memset(z, 0, sizeof(z)), ans = 0;
	while(1 + z[1] <= len1 && 1 + z[1] <= len && s1[1 + z[1]] == s[1 + z[1]]) z[1]++;
	/*
	  单独求 z[1],否则会导致 L = 1,R = min(len, len1)
	  遍历 s1[2..len1] 时,对于 s1[i],每次都有 i <= R
	  它的 pos 为 i - L + 1 = i,从而 z[i] = z[i]
	  这样就无法达到复用之前信息的目的,不能优化时间复杂度 
	*/
	for(int i = 2; i <= len1; i++)
	{
		if(i <= R) // 如果当前字符在匹配段 s[L..R] 内 
		{
			int pos = i - L + 1; // 求出 i 对应到 s[1..R-L+1] 中的位置 
			z[i] = min(z[pos], R - i + 1); // 为了防止 i + z[pos] + 1 超出匹配段,这里取 min 
		}
		while(i + z[i] <= len1 && 1 + z[i] <= len && s1[i + z[i]] == s[1 + z[i]]) z[i]++;
		// 对于当前字符不在匹配段内的,或者 i + z[pos] + 1 超出匹配段的,用朴素算法扩展 z[i] 
		if(i + z[i] - 1 > R) L = i, R = i + z[i] - 1;
	}
	for(int i = 1; i <= len1; i++) ans ^= 1ll * i * (z[i] + 1);
	printf("%lld\n", ans);
}

int main()
{
//	freopen("P5410_1.in", "r", stdin);
	scanf("%s%s", a + 1, b + 1);
	getz(b, b), getz(b, a);
	return 0;
}
2023/10/17 18:25
加载中...