2019/4/22 kmp模板

这里是从头到尾彻底理解KMP的一篇博客,写的非常好：https://blog.csdn.net/v_JULY_v/article/details/7041827

题意：输入多组样例,每组给定一个模式串S,文本串T,问S在T中出现的次数

这道题主要是为了记录一下kmp的模板, 我太菜了,不能彻底理解 ,先记着吧

 1 void get_next() //获得模式串next数组 
 2 {
 3     s_len = strlen(s);//模式串 
 4     next[0] = -1;
 5     int j = 0, k = -1;
 6     while(j < s_len)
 7     {
 8         if(k == -1 || s[j] == s[k])
 9         {
10             j ++, k ++;
11             next[j] = k;
12         }
13         else
14             k = next[k];
15     }
16 }

 1 void kmp() //输出模式串在文本串中出现次数 
 2 {
 3     ans = 0;
 4     int i = 0, j = 0; //i文本串 j模式串 
 5     while(i < str_len)  //遍历文本串 
 6     {
 7         if(s[j] == str[i] || j == -1)
 8         {
 9             i ++, j ++;
10         }
11         else
12             j = next[j];
13         if(j == s_len)
14         {
15             ans ++;
16             j = next[j];
17         }
18     }
19     printf("%d\n", ans);
20 }

 1 void kmp()//输出模式串在文本串中的各个位置 ,没找到输出-1 
 2 {
 3     int flag = 0;
 4     int i = 0, j = 0;
 5     while(i < str_len) //遍历文本串
 6     {
 7         if(j == -1 || s[j] == str[i])
 8         {
 9             j ++, i ++;
10         }
11         else
12             j = next[j]; //回到上一个j位置字符的位置 
13         if(j == s_len)
14         {
15             if(!flag)
16                 printf("%d", i - j);
17             else
18                 printf(" %d", i - j);
19             flag = 1;
20             j = next[j]; //回到模式串开头位置,重新找在文本串中找 
21         }
22     }
23     if(!flag)
24         printf("-1\n");
25     else
26         printf("\n");
27 }

以上三个模板字符串的下标是从 0 开始的。例如s = "ab", str = "ababab"。则输出3次，位置分别为0 2 4