3336记忆化搜索解题报告

起初也不知道这个题目还有一个更为简单易想的办法，那就是记忆化的搜索。

因为题目的基本意思就是要你匹配给你字符串的所有长度的前缀在字符串当中所出现的次数，那么这个时候我们可以设计一个简便的记忆方法。

设置一个place来记录每次新的前缀长度所匹配的位置信息。

例如 ababab这个字符串

我们可以首先让这个place数据

先匹配“a”字符串，那么匹配a的位置信息就是

Place={1,3,5}一共三次

然后匹配"ab"字符串，只用在以前place的基础上匹配后面跟的'b'就行，因为只有出现过'a'的位置才可能匹配"ab"字符串，所以第二次匹配，place数据信息为：

Place={2,4,6};一共匹配了三次，

这样就可以轻易算出"a""ab"两个前缀的匹配次数，之后都是同样的道理。

代码如下：

#include<stdio.h>
using namespace std;
int main()
{
  int T,len;
  char temp[200002],pos;
  int  place[200002]; 
  scanf("%d",&T);
  while(T--)
  {
     scanf("%d",&len);
     getchar();
     gets(temp+1);
     int k=0,total=0,t;
     pos=temp[1];
     for(int i=1;i<=len;i++)
     {
        if(temp[i]==pos)
        {
           place[k++]=i;   
           total++; 
        }        
     }
     total%=10007; 
     for(int i=2;i<=len;i++)
     {
        t=k;
        k=0;
        pos=temp[i];
        for(int j=0;j<t;j++)
        {
          if(temp[place[j]+1]==pos)
          {
            place[k++]=place[j]+1;
            total++;                         
          } 
        }
        total%=10007;
     }
     printf("%d\n",total);   
  } 
  return 0;    
}