关于 num[1]=1 的解释和 num[1]=0 AC做法

本题目题解区一直都是 num[1]=1，却没人解答

我的代码和各位的题解可以几乎相似，但是我并没有 num[1]=1，按题目意思来说应该是 num[1]=0

如果按照 num[1]=0 经过递推后得到的答案是 num[i]，表示

i

位置开始的后缀和原串的前缀相同的数量（含重叠）

在 num[1]=0 的情况下，我们来看样例中 abcababc

结果如下

字串 a b c a b a b c
next 0 0 0 1 2 1 2 3
num  0 1 1 1 2 1 2 2

然后我发现对于没有公共前缀的第二位置 ab 和第三个位置 abc 他们的 num 应该是

0

而不是

1

，这错误的原因是：他们的 next 是

0

，也就意味着没有公共前后缀，但是我们递推时确实按照 num[0]+1 进行操作，所以出现了错误。

这里出现错误，那么显然再往后地推的时候必然后方也会部分出现错误。改正的话就是如果没有公共前后缀，即 next[i]=0 不算递推贡献。

还有一个小地方

我们在求答案时，是找到和

i

位置没有重叠公共前后缀 j 也就是代码中的 while ((j<<1)>i) j=kmp[j];

再看接下来的代码（题解区）：

cnt=(cnt*(ll)(ans[j]+1))%MOD;//记得+1

此时我们将

j

作为

i

位置的答案记录贡献，这存在一个问题，看如下例子：

abnvmfjdsckja 对于前后的两个 a ，如果按照代码流程来的话，最后一个 a 的位置记录答案的贡献应该是 ans[1] ，这少了什么？少了 a...a 这种组合，同理我们可以再找剧组样例，按算法流程来的话，确实类似 abc....abc 的组合确实都不会统计在贡献内，他只会总计 ans[3] 即前面 abc 的贡献，忽略了这个组合贡献

针对这，我们只需要在贡献时 +1 即可，但还会有 j=0 的情况，此时就不存在公共前后缀了，所以不会产生组合贡献，特判一下，那么算法代码就变成：

sum=(sum*(ans[j]+1*(j!=0)+1)%mod+mod)%mod;

至此，我们解决了如何在 num[1]=0 满足题目含义下，正确的AC这道题目。翻题解区时确实各位大佬对于 num[1]=1 总是一笔带过或者以显然寥寥草事，起码还是有部分人在问这个问题，所以就算显然，也需要解释一下。

为什么 num[1]=1 也可以（其实是我想卡他，但是发现了二者间的相似性）

对于 kmp 的算流程，我们是忽略第一个位置的，都是从第二个位置开始求 nxet ，

+1

的目的其实就是上面我说的组合贡献的计算，对于 nxet[i]=0 的位置，在 kmp 中都按照递推式子都变成 num[0]+1 ，

这 +1 其实就是组合贡献，之所以 num[1]=1 是因为，在 kmp 中 1 位置直接被忽略过了，没有进行递推，因此这里特别的给 num[1]=1 ，保证在以后的递推中存在由 1 位置递推过来的，并算上此时的组合贡献

注：以上均为本人看法，可在讨论区，给部分不懂的同学阅读，若有不合适的地方，请各位大佬提出。

下面是 AC 代码，里面有针对 num[1]=1 的屏蔽注释。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int B=1e6+10;
int j;
int kmp[B];
int lb;
int ans[B];
int T;
char b[B];
const int mod=1e9+7;
void solve()
{
	j=0;
	cin>>b+1;
	lb=strlen(b+1);
	for (int i=0;i<=lb;i++) ans[i]=kmp[i]=0;
//	ans[1]=1;
	for (int i=2;i<=lb;i++)
	{
		while (j && b[j+1]!=b[i]) j=kmp[j];
		if (b[j+1]==b[i]) j++;
		kmp[i]=j;
//		if (j==1) ans[i]=2;
		if (!j) ans[i]=0;
		else ans[i]=ans[j]+1;
	}
	j=0;
	int sum=1;
	for (int i=2;i<=lb;i++)
	{
		while (j && b[j+1]!=b[i]) j=kmp[j];
		if (b[j+1]==b[i]) j++;
		while ((j<<1)>i) j=kmp[j];
		sum=(sum*(ans[j]+1*(j!=0)+1)%mod+mod)%mod;
	}
	printf("%lld\n",sum);
	return;
}
signed main()
{
	cin>>T;
	while (T--) solve();
}
/*
1
abcababc
*/

关于 num[1]=1 的解释和 num[1]=0 AC做法

讨论操作

本题目题解区一直都是 num[1]=1，却没人解答

回复

相关推荐

关于 num[1]=1 的解释和 num[1]=0 AC做法