hdu 3336【Count the string】(KMP)

一道字符串匹配的题目，仅仅借此题练习一下KMP

因为这道题目就是要求用从头开始的n个字符串去匹配原来的字符串，很明显与KMP中求next的过程很相似，所以只要把能够从头开始匹配一定个数的字符串的个数加起来就OK了（再此结果上还应该加上字符串的长度，因为每个从头开始的字符串本身也可以去匹配自己的），即将next中值不为-1和0的个数统计出来即可。

用GCC编译的，时间用了46MS。

 #include <stdio.h>

 #include <string.h>

 #define MAXLEN 200005

 #define MOD 10007

 int next[MAXLEN];

 char myChar[MAXLEN];

 int getNext()

 {

     int i = ,j = -;

     int sum = ;

     int len = strlen(myChar);

     memset(next,,sizeof(int));

     next[i] = j;

     while(i < len)

     {

         if(j == - || myChar[i] == myChar[j])

         {

             i ++;

             j ++;

             next[i] = j;

             if(j != - && j != )

             {

                 sum ++;

                 sum = sum % MOD;

             }

         }

         else

         {

             j = next[j];

         }

     }

     return sum;

 }

 int main()

 {

     int n,m;

     scanf("%d",&n);

     while(n --)

     {

         scanf("%d",&m);

         memset(myChar,,sizeof(char));

         scanf("%s",myChar);

         printf("%d\n",(getNext()+m)%MOD);

     }

     return ;

 }

代码如下：

巴特西

hdu 3336【Count the string】(KMP)

最新文章

热门文章