学步园

http://acm.hdu.edu.cn/showproblem.php?pid=3336 

题意：给定一个长度为n的字符串（0<n<20000），以n的前k个字符组成一个前序（k = 1,2,3,4.....n），在n中找与前序相同的子序列的个数。

所谓的记忆化搜索，是因为前一次的搜索对后面的搜索有帮助，就记录下来，这样可以减少后面搜索的时间。

看看样例：

abab

前序是 a，ab，aba，abab

建立一个num数组，记录每一个与前序相同的字串的头下标。

因为只有想要与一个前序相同，必先要与上一个前序相同，所以每次只要比较前序最后的一个元素是否与下标为num[k]加上前序长度的元素相同就可以了。

#include <stdio.h>
int main ()
{
	int t,n,i,j,k,sum,all,len;//len是记录前序长度的
	char ch[200010],ch1,ch2;
	int num[200020],nn;//nn是记录num数组中元素的个数，每比较完一次元素就更新一次
	scanf ("%d",&t);
	while (t-- > 0)
	{
		len = 0;
		scanf ("%d%c",&n,&ch2);
		gets(ch);
		for (i = 0 ; i < n ; i ++)
			num[i] = i ;
		nn = n;	
		sum = 0;
		for (i = 0 ; i < n ; i ++)
		{
			ch1 = ch[i];
			int ji = 0;
			for (j = 0 ; j < nn ; j ++)
			{
				if (num[j] + len < n && ch1 == ch[num[j] + len] && num[j] + len < n)
				{
					sum ++;
					sum = sum % 10007 ;
					num[ji ++] = num[j];
				}
			}
			nn = ji;
			len ++;
		}
		printf ("%d\n",sum);
	}
}