杭电 hdu 3336 Count the string

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.

URL   : http://acm.hdu.edu.cn/showproblem.php?pid=3336
Name  : 3336 Count the string

Date  : Monday, August 22, 2011
Time Stage : one hours

Result:
4472537	2011-08-22 20:43:06	Accepted	3336
31MS	1988K	1616 B
C++	pyy


Test Data:


Review:
这题有意思～～～一开始不知道怎么做，后来参考了一下别人的思想，就A了

此题用到kmp算法中getNext函数的思想，更准确地来说，是未优化过的getNext函数的思想。
用未优化过的getNext函数输出字符串的信息如下：
 0 1 2 3 4 5 6 7 8 9
 a b a b c d a b d
-1 0 0 1 2 0 0 1 2 0
可以发现，给出任意数字i，设它的next 值为j (j > 0)，则j-1 的值表示：
以pattn[0]...pattn[j-1]开头的前缀，在主串中出现了一次。
比如上表中i=4，则next[4] = 2，表示以pattn[0]...pattn[1] 为开头的前缀
（即：a b）在主串出现了一次（这里的一次，不是说“到目前为至只出现一次”的意思，
而是从i 的位置往前数，能数到一次，当然再往前数还有一次。）。
当i=8 时，情况也是一样的。

有人可能会觉得，当i=2 时，next[2] = 0 啊，怎么跟上面的说法不一样？
这是因为上面的方法只适用于前缀第二次或者第二次以上出现的情况。
正如下文所描述的那样，记录第一次出现的情况，可以用++count[i];
第二次及以上的情况，就用++count[j-1];　来记录了
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define infinity    0x0f0f0f0f
#define minus_inf    0x80808080

#define MAXSIZE	200009

int tcase, n, lenP ;
int next[MAXSIZE], count[MAXSIZE] ;
char pattn[MAXSIZE] ;

void getNext ()
{
	int i, j ;
	i = 0 ;
	j = -1 ;
	next[0] = -1 ;
	memset (count, 0, sizeof (count)) ;
	while (i < lenP)
	{
		if (j == -1 || pattn[i] == pattn[j])
		{
			++count[i] ;	// 此处记录以pattn[0]...pattn[i]为前缀的单词
							// 第一次出现的情况
			++i ;
			++j ;
			next[i] = j ;
			
			// 下面记录以pattn[0]...pattn[j-1]为前缀的单词出现两次以上的情况
			if (j > 0)
				++count[j - 1] ;
			// 下面是getNext 的优化算法，但此处用不上
/*			
			if (pattn[i] != pattn[j])
				next[i] = j ;
			else
				next[i] = next[j] ;
*/				
		}
		else
			j = next[j] ;			
	}
}

int main ()
{
	int i, sum ;
	while (scanf ("%d", &tcase) != EOF)
	{
		while (tcase--)
		{
			scanf ("%d", &lenP) ;
			scanf ("%s", pattn) ;
			getNext () ;
#if 0
			for (i = 0 ; i <= lenP ; ++i)
				printf ("%d ", next[i]) ;
			puts ("") ;
			for (i = 0 ; i < lenP ; ++i)
				printf ("%d ", count[i]) ;
			puts ("") ;
#endif
			sum = 0 ;
			for (i = 0 ; i < lenP ; ++i)
				sum += count[i] ;
			printf ("%d\n", sum % 10007) ;
		}
	}
	return 0 ;
}