HDU-3363 Count the string KMP 巧用next函数

　　正如题目所说，该题正是巧用next函数求得的，题目意思：给定一个串，求以它自身长度为（1，2，3…… N）的子串作为模式串，以完整的自身作为母串，求最后所得到的总匹配数。  其中样例中的 abab 结果是 6（ a 出现两次， ab出现两次， abc出现一次， abcd出现一次 ）， aaaa的输出结果应该为 10 （ a出现四次， aa出现三次， aaa出现两次， aaaa出现一次 ）。

　　还记得前面三道KMP题，一道（1711）是搜索返回是否成功匹配，一道（2087）是搜索模式串出现多少次（母串不可重复计算）， 最后一道（1686）同样是搜索模式串出现多少次（当然母串可以重复计算），难度是依次递增。这次这道题目也算是在第三题的基础上演变而来，本来以为这一题与1686差不多，我找出所有第一个字母出现的下表，收集为一个索引表，然后再进行KMP匹配，每次只要匹配到一个字母那么以这个字母的前缀匹配数就加上一。数据是过了，但也只有在超时时才追悔莫及。

　　其实在写KMP的时候就觉得很像getnext(  )函数，因为我正在做的事情就是将自己与本身串进行比较。最终的结果说明，这里只需运行一个getnext(  )函数就能够将此题解决，因为这很好了贴切了这个题目的意思，将自身与自身进行匹配。

　　现就串 ababababa 进行拆解：

　　1. 首先运行getnext(  )函数，我们将会得到这个串的 next[] 表，这里可以得到 next[] 表：

　　    A.  011234567   

     2. 再对next[]表的意义做进一步分析，首先我们应该明确所有的字符对应next[]值均是由上一个字符匹配的结果所得到的，这也解释了为什么我们要单独将next[1]赋为0，要知道这时候我们的匹配工作还没有开始。设k= next[i]， k的值的意思是说，到 i- 1 号 字符，并且以 i- 1 号为终点，以某一点为起点，与本身从 1 号字符开始成功且最大可能的与本身匹配了k个字符（方向均为从左到右）。即满足  str[ 1, 2, 3…… k- 1 ]= str[ i- k+ 1, i- k+ 2, i- k+ 3…… i- 1 ]，由于在求next的过程中，每次匹配成功我们并没有回溯模式串的指针，因此这样能够保证每个next[]的值均是最大的。回到问题上来，看如何利用next[]值来解决这道题目，第一个字符next[]值无意义，因为首字符的前面谈不上匹配成功。从第二个字符开始，A串的意思： （注意橙色字体） 可以转化为 001234567 这就是还原了之后的匹配值( 处理时就是在 自增之前进行处理 )，即每一位表示到当前位置时，最多匹配了多少字符。

　　3. 最后分析如何计算前缀匹配总值，这里我们需要重新开辟一个数组来记录到达每一字符时会新出现多少个前缀匹配，用rec[]表示，初始化rec[1]= 1; 这表示到第一个字符时，就与自身匹配构成1种情况。 已知第5个字符的匹配值为3，那么到达这个字符时的那么新出现的匹配前缀应该为 rec[3]+ 1, 前面的rec[3]是因为这里出现了前三个字符的重复段，后面的 1 是因为 str[1-5] 本身的一个前缀串。 理清了这些关系，代码就可以写下来了。

　　代码如下：

#include <iostream>
#include <cstring>

using namespace std;

char mix[200005];   /*_*/   int next[200005], rec[200005];

void getnext( char *s, int *n )
{
	int k= 1, j= 0, len= strlen( s+ 1 );
	next[1]= 0, rec[1]= 1;
	while( k<= len )
	{
		if( j== 0|| s[k]== s[j] )
		{
		    rec[k]=( rec[j] + 1 )% 10007;
			++k, ++j;
		    n[k]= j;
		}
		else
		{
			j= n[j];
		}
	}
}

int main(  )
{
	int T, N;
	cin>> T;
	while( T--&& cin>> N )
	{
		memset( rec, 0, sizeof( rec ) );
		cin>> mix+ 1;
		int len= strlen( mix+ 1 ), ans= 0;
		getnext( mix, next );
		for( int i= 1; i<= len; ++i )
		{
			ans+= rec[i]% 10007;
		} 
		ans %= 10007;
		cout<< ans<< endl;
	}
}