`

【KMP】HDU 3336 Count the string

    博客分类:
  • KMP
阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=3336


题意:求字串中【前缀+跟前缀相同的子串】的个数?

Sample Input
1
4
abab

Sample Output
6

abab:包括2个a,2个ab,1个aba,1个abab


这里要用到next值的意义:
next[i]表示前i个字符所组成的字符串最大前后缀匹配长度
举个例子:

next[5]=2, 表示下标5前面那个字符串abcab的前后缀匹配的最大长度是2,显然就是ab了

回到本题:
所求=字串的前缀个数+与前缀相同的子串
问题可以部分转化为:每个前缀的最大前后缀匹配问题

继续用上面的例子:

第一步:

对于这段子串,next[5]=2,然后后面不符合next值的递推规律了
所以对于abcab,长度为2的后缀,即ab与前缀匹配
所以+1个ab,注意还要+1个a,既然后缀ab跟前缀ab匹配,则必有a跟前缀匹配
也就是+2个了,其实实际上+next[5]就可以了,因为这是最长前后缀匹配长度

第二步:

对于这段子串:
next[6]=1,然后后面不符合next值的递推规律了
所以对于abcaba,长度为1的后缀,即a与前缀匹配
所以+1个a,也就是+next[6]了

第三步:

对于整个串:
next[12]=4后面没有了
所以对于整个串:abcabacbabca,长度为4的后缀跟前缀匹配
所以+1个abca,+1个abc,+1个ab,+1个a,总共+4个,也就是+next[12]了

最后:
好了,刚刚一共+了7个与前缀匹配的子串
上面说了题目是求:字串的前缀个数+与前缀相同的子串个数
与前缀相同的子串个数就是7个了
然后字串的前缀个数当然就是整个串的长度了,那么就是12个
加起来就是答案:19


#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define L2 200005

int next[L2], len2;
char p[L2];

void get_next ()    //KMP原始next值
{
	int j = 0, k = -1;
	next[0] = -1;
	while (j < len2)
	{
		if (k == -1 || p[j] == p[k])
		{
			j++, k++;
			next[j] = k;
		}
		else k = next[k];
	}
}
int main()
{
	int t, res, j;
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d%s", &len2, p);
		get_next ();
		res = next[len2] + len2;	//先包含:最后的next值【第三步】+前缀数【串长】  
		for (j = 0; j < len2; j++)
			if (next[j] > 0 && next[j] + 1 != next[j+1])
				res += next[j];		//当不满足递推规律时+next值【第一、二步】  
		printf ("%d\n", res%10007);
	}
	return 0;
}
1
2
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics