hdu 3336 kmp+next数组应用

分析转自：http://972169909-qq-com.iteye.com/blog/1114968

十分易懂

题意：求字串中【前缀+跟前缀相同的子串】的个数？

Sample Input
1
4
abab

Sample Output
6

abab：包括2个a，2个ab，1个aba，1个abab

这里要用到next值的意义：
next[i]表示前i个字符所组成的字符串的最大前后缀匹配长度
举个例子：
hdu 3336 kmp+next数组应用
next[5]=2, 表示下标5前面那个字符串abcab的前后缀匹配的最大长度是2，显然就是ab了

回到本题：
所求=字串的前缀个数+与前缀相同的子串
问题可以部分转化为：每个前缀的最大前后缀匹配问题

继续用上面的例子：

第一步：
hdu 3336 kmp+next数组应用
对于这段子串，next[5]=2，然后后面不符合next值的递推规律了
所以对于abcab，长度为2的后缀，即ab与前缀匹配
所以+1个ab，注意还要+1个a，既然后缀ab跟前缀ab匹配，则必有a跟前缀匹配
也就是+2个了，其实实际上+next[5]就可以了，因为这是最长前后缀匹配长度

第二步：
hdu 3336 kmp+next数组应用
对于这段子串：
next[6]=1，然后后面不符合next值的递推规律了
所以对于abcaba，长度为1的后缀，即a与前缀匹配
所以+1个a，也就是+next[6]了

第三步：

对于整个串：
next[12]=4后面没有了
所以对于整个串：abcabacbabca，长度为4的后缀跟前缀匹配
所以+1个abca，+1个abc，+1个ab，+1个a，总共+4个，也就是+next[12]了

最后：
好了，刚刚一共+了7个与前缀匹配的子串
上面说了题目是求：字串的前缀个数+与前缀相同的子串个数
与前缀相同的子串个数就是7个了
然后字串的前缀个数当然就是整个串的长度了，那么就是12个
加起来就是答案：19

以前代码错了居然也能A，这数据。。。

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int MAXN=200020;
 4 const int MOD=10007;
 5 int dp[MAXN];
 6 char str[MAXN];
 7 int next[MAXN];
 8 
 9 void getNext(char *p)
10 {
11     int j,k;
12     j=0;
13     k=-1;
14     next[0]=-1;
15     int len=strlen(p);
16     while(j<len)
17     {
18         if(k==-1||p[j]==p[k])
19         {
20             j++;
21             k++;
22             next[j]=k;
23         }
24         else k=next[k];
25     }
26 }
27 int main()
28 {
29     int T;
30     int n;
31     //freopen("1.in","r",stdin);
32     scanf("%d",&T);
33     while(T--)
34     {
35         scanf("%d",&n);
36         scanf("%s",&str);
37         getNext(str);
38         dp[0]=0;
39         int ans=0;
40         for(int i=1;i<=n;i++)
41         {
42             if(next[i]) ans++;
43             ans%=MOD;
44         }
45         ans+=n;
46         ans%=MOD;
47         printf("%d
",ans);
48     }
49     return 0;
50 }

hdu 3336 kmp+next数组应用

相关推荐