icontofig | 发布于 2019-07-20 21:56:59 | 阅读量 313 | KMP
发布于 2019-07-20 21:56:59 | KMP

题目大意

求给定的字符串所有前缀在字符串中出现次数的总和mod10007的值

题解

这题的结论是这样的:求出next数组,然后从后向前,依次累加……

算了我也说不明白,还是给个代码合适。。。。

for(int i = 1;i <= n;++i){
	a[i] = 1;
}
for(int i = n;i >= 1;--i)
    a[nxt[i]] += a[i];

就是这样的一个结论,然后O(n)就能求出所有我们要的结果。

其中ai代表以当前位置i为结尾的前缀字符串在原字符串中出现的次数。

为什么这样可以做?
我个人的想法是……KMP中的next数组,实际上表示的真正含义为到位置pos为止的前缀字符串中,最长的能够匹配的前缀和后缀的长度(这里的前缀和后缀值得是我们取出的前缀字符串的前缀和后缀,而且这里的前缀和后缀的长度不能和取出的这个前缀字符串的长度相等)。

于是我们想,如果我们取出一个前缀,结束位置为pos,他出现过x次,那么他对应的以next[pos]为结尾的前缀字符串一定也会随着这个前缀串出现x+1次。但是这其中还有一次是会不断算重复的,于是累加的时候就加x,把本身有的那一次放入初始化的时候,先对每个位置的值赋值1。

其实我也不是很明白这样正确性怎么证明,但是毕竟icpc吗,要大胆猜想……

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
const int maxn = 2e5+5;
int cas;
char s[maxn];
int a[maxn];
int nxt[maxn];
void KMP(){
	int j = 0;
	nxt[1] = 0;
	int len = strlen(s+1);
	for(int i = 2;i <= len;++i){
		while(j && s[i] != s[j+1])j = nxt[j];
		if(s[j+1] == s[i])j++;
		nxt[i] = j;
	}
	return;
}
int T;
const int mod = 10007;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		getchar();
		scanf("%s",s+1);
		KMP();
		for(int i = 1;i <= n;++i){
			a[i] = 1;
		}
		int ans = 0;
		for(int i = n;i >= 1;--i){
			a[nxt[i]] += a[i];
			a[nxt[i]] %= mod;
			ans += a[i];
			ans %= mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}



内容更新于: 2019-07-20 21:57:00
链接地址: http://blog.leanote.com/post/icontofig/b4795d440a9b

上一篇: Light OJ 1258 Making Huge Palindromes KMP构造回文串

下一篇: Codeforces Round #2 The least round way DP+贪心

313 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航