2019/4/22 kmp模板

题目连接：传送门!!!

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

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

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

 void get_next() //获得模式串next数组
 {
     s_len = strlen(s);//模式串
     next[] = -;
     int j = , k = -;
     while(j < s_len)
     {
         if(k == - || s[j] == s[k])
         {
             j ++, k ++;
             next[j] = k;
         }
         else
             k = next[k];
     }
 }

　　

 void kmp() //输出模式串在文本串中出现次数
 {
     ans = ;
     int i = , j = ; //i文本串 j模式串
     while(i < str_len)  //遍历文本串
     {
         if(s[j] == str[i] || j == -)
         {
             i ++, j ++;
         }
         else
             j = next[j];
         if(j == s_len)
         {
             ans ++;
             j = next[j];
         }
     }
     printf("%d\n", ans);
 }

　　

 void kmp()//输出模式串在文本串中的各个位置 ,没找到输出-1
 {
     int flag = ;
     int i = , j = ;
     while(i < str_len) //遍历文本串
     {
         if(j == - || s[j] == str[i])
         {
             j ++, i ++;
         }
         else
             j = next[j]; //回到上一个j位置字符的位置
         if(j == s_len)
         {
             if(!flag)
                 printf("%d", i - j);
             else
                 printf(" %d", i - j);
             flag = ;
             j = next[j]; //回到模式串开头位置,重新找在文本串中找
         }
     }
     if(!flag)
         printf("-1\n");
     else
         printf("\n");
 }

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