kmp hdu 3336 下标从1开始

kmp 模板

数组下标从1开始 P[1,2, . . . m] T[1,2 ,3 ... n]

void Prefix_Func()
 {
     int i,k;
     k=0;
     next[1]=0;
     for(i=2;i<=m;i++)
     {
        while(k>0 && P[k+1]!= P[i])
            k=next[k];
        if(P[k+1] == P[i])
            k++;
        next[i]=k;
     }
 }

数组下标从0开始

void Prefix_Func()
 {
     int i,k;
     k=-1;
     next[0]=-1;
     for(i=1;i<m;i++)
     {
        while(k>=0 && P[k+1]!= P[i])
            k=next[k];
        if(P[k+1] == P[i])
            k++;
        next[i]=k;
     }
 }

注意的地方：

a,表示从0开始 b, 表示从1开始

1， a, 初始 next[0] = -1

b, next[1] = 0

2, i 的取值范围

a, 一个是 [1------m-1 ]

b, 一个是 2--------m

3， while 循环终止条件

a, 一个是 k>=0

b, 一个是 k>0

hdu 3336 计算模板中前缀的个数

//设dp[i] :以string[i]结尾的字符字串的前缀总数
// 结论： dp[j]= dp[i] +1 , 其中 next[j] = i

代码如下：本题最好用下标从1开始

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string>
 4 #include<string.h>
 5 #define N 200005
 6 using namespace std;
 7 char P[N];
 8 int dp[N];
 9 int n,m;
10 int next[N];
11  void Prefix_Func()
12  {
13      int i,k;
14      k=0;
15      next[1]=0;
16      for(i=2;i<=m;i++)
17      {
18         while(k>0 && P[k+1]!= P[i])
19             k=next[k];
20         if(P[k+1] == P[i])
21             k++;
22         next[i]=k;
23      }
24  }
25 int main()
26 {
27     int t,sum;
28     cin>>t;
29     while(t--)
30     {
31         sum=0;
32         cin>>m;
33         scanf("%s",P+1);
34         Prefix_Func();
35         dp[0]=0;
36         for(int i=1;i<=m;i++)
37             dp[i]=dp[next[i]]+1;
38 
39         for(int i=1;i<=m;i++)
40         {
41             sum=(sum+dp[i])%10007;
42         }
43         cout<<sum<<endl;
44     }
45     return 0 ;
46 }