hdu 3336 Count the string

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3336

//这题的题意就是给出一个字符串S，求其前缀的子串与该串共有多少个匹配

开始这题理解错题意了，后来明白就简单多了，不过这题有两个优化，要不容易超市

1.对于其子串不必求出所有子串的next数组，只需要求出原串的next，其子串的next则也包含在内

2.当调用KMP时某子串只匹配了一次，那么下面则无需再次调用KMP，解释：如果S是abcabcd,那么当abca只出现一次

那么后面所有前缀子串则只可能匹配一次，例如子串abcab,abcabc,等

代码如下

View Code

 1 # include <stdio.h>
 2 # include <string.h>
 3 # define mod 10007
 4 const int NN=200000;
 5 char s[NN+20],p[NN+20];
 6 int next[NN+20],cnt;
 7 int lens,lenp;
 8 void COUNT_next(char *s)
 9 {
10 
11     next[0] = 0;
12     int k=0,q;
13     for(q=1; q<lens; q++)
14     {
15         while(k>0 && p[k]!=p[q])
16             k=p[k];
17         if(p[k] == p[q])
18             k++;
19         next[q]=k;
20     }
21 }
22 int KMP(char *str,char *p)
23 {
24     int q=0,i;
25     cnt=0;
26     for(i=0; i<lens; i++)
27     {
28         while(q>0 && p[q]!=s[i])
29             q=p[q];
30         if(p[q]==s[i])
31         {
32             q=q+1;
33             if(q==lenp)
34             {
35                 q=0;
36                 cnt++;
37             }
38         }
39         else q=p[q];
40     }
41     return cnt;
42 }
43 int main()
44 {
45     int t, n, i, q, k;
46     scanf("%d",&t);
47     while(t--)
48     {
49         scanf("%d %s", &n, s);
50         int sum=0,k;
51         lens=strlen(s);
52         COUNT_next(s);
53         for(i=0; i<n; i++)
54         {
55             p[i]=s[i];
56             lenp=i+1;
57             k=KMP(s,p);
58             sum+=k;
59             if(k==1)  //这里是第二个优化
60             {
61                 sum=(sum+(n-i-1));
62                 break;
63             }
64         }
65         printf("%d\n",sum%mod);
66     }
67     return 0;
68 }

其实我一开始写的时候也没注意第二个优化，超时好几次

第一篇博文~~~