【BZOJ3670】【NOI2014】动物园（KMP算法）

时间：2023-03-08 19:12:06

【BZOJ3670】动物园（KMP算法）

题面

BZOJ

题解

神TM阅读理解题

看完题目之后

想暴力：

搞个倍增数组来跳\(next\)

每次暴跳\(next\)

复杂度\(O(Tnlogn)\)

算一下，感觉复杂度差不多呀

很果断的交了一发

然后\(80\)分。。。

暴力代码送上：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MOD 1000000007

char s[1200000];

int nt[1200000];

int jp[1200000][21];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%s",s+1);

		nt[1]=0;

		int l=strlen(s+1);

		for(int i=2;i<=l;++i)

		{

			int j=nt[i-1];

			while(j&&s[i]!=s[j+1])j=nt[j];

			if(s[i]==s[j+1])nt[i]=j+1;

			else nt[i]=0;

			jp[i][0]=nt[i];

		}

		for(int j=1;j<20;++j)

			for(int i=1;i<=l;++i)

				jp[i][j]=jp[jp[i][j-1]][j-1];

		int ans=1;

		for(int i=2;i<=l;++i)

		{

			int tt=i;

			for(int j=19;j>=0;--j)

				if(jp[tt][j]*2>i)tt=jp[tt][j];

			int gg=0;

			for(int j=19;j>=0;--j)

				if(jp[tt][j])gg+=1<<j,tt=jp[tt][j];

			ans=1ll*ans*(gg+1)%MOD;

		}

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

	}

	return 0;

}

然后我很不爽

把倍增数组的两维反了过来，防止反复横跳

然后我就\(AC\)了？？？

又一次感受到玄学强大的力量

这个\(O(Tnlogn)\)的复杂度果然很对呀。。。

暴力能AC？？？：

（BZOJ上都能AC？？？）

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MOD 1000000007

char s[1200000];

int nt[1200000];

int jp[21][1200000];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%s",s+1);

		nt[1]=0;

		int l=strlen(s+1);

		for(int i=2;i<=l;++i)

		{

			int j=nt[i-1];

			while(j&&s[i]!=s[j+1])j=nt[j];

			if(s[i]==s[j+1])nt[i]=j+1;

			else nt[i]=0;

			jp[0][i]=nt[i];

		}

		for(int j=1;j<20;++j)

			for(int i=1;i<=l;++i)

				jp[j][i]=jp[j-1][jp[j-1][i]];

		int ans=1;

		for(int i=2;i<=l;++i)

		{

			int tt=i;

			for(int j=19;j>=0;--j)

				if(jp[j][tt]*2>i)tt=jp[j][tt];

			int gg=0;

			for(int j=19;j>=0;--j)

				if(jp[j][tt])gg+=1<<j,tt=jp[j][tt];

			ans=1ll*ans*(gg+1)%MOD;

		}

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

	}

	return 0;

}

经历了这么滑稽的事情

还是想想有没有更加好的复杂度。。。

考虑记录一个数组\(cnt[i]\)

表示从\(i\)位置最多能够往前跳的次数

很明显的，\(cnt[i]=cnt[next[i]]+1\)

现在，我们只需要知道每一个位置能够跳到哪里就行了

还是最简单的暴力

每次从当前位置\(i\)开始，暴力向前跳到\(k\)

直到\(k*2<i\)为止，然后答案累乘\(cnt[k]+1\)

看起来每次暴跳的时间复杂度不太能够接受

最坏可以打到\(O(n^2)\)

但是考虑\(next\)数组是怎么求出来的

每次沿着前一个字符的\(next\)跳

直到找到一个合法的位置

因此，我们模仿这个过程

假设上一个字符跳到了\(k\)

那么，当前位置最多跳到\(k+1\)

很容易证明

假设当前位置跳到了一个合法的位置\(k'\)

那么，当前位置的前一个位置，必定可以跳到一个合法位置\(k'-1\)

所以，我们只需要类似\(KMP\)，每次利用上一次求出来的\(k\)接着跳就行了

这样的时间复杂度近似\(O(n)\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define rg register

#define MOD 1000000007

char s[1200000];

int nt[1200000];

int cnt[1200000];

int main()

{

	rg int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%s",s+1);

		nt[1]=0;

		rg int l=strlen(s+1);

		for(rg int i=2;i<=l;++i)

		{

			rg int j=nt[i-1];

			while(j&&s[i]!=s[j+1])j=nt[j];

			if(s[i]==s[j+1])nt[i]=j+1;

			else nt[i]=0;

		}

		cnt[1]=1;

		rg int ans=1;

		for(rg int i=2;i<=l;++i)cnt[i]=cnt[nt[i]]+1;

		for(rg int i=2,k=0;i<=l;++i)

		{

			while(k&&s[k+1]!=s[i])k=nt[k];

			if(s[i]==s[k+1])k++;

			while(k*2>i)k=nt[k];

			ans=1ll*ans*(cnt[k]+1)%MOD;

		}

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

	}

	return 0;

}

相关文章