KMP算法

奥普瓯江

原理：

备注：

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void str_next(int stri_1[], char strc_2[]);
void str_next(int stri_1[], char strc_2[])
{
    stri_1[0] = -1;
    int k = -1;

    for(int i = 1; i < strlen(strc_2); i++)
    {
        while(k > -1 && strc_2[k + 1] != strc_2[i] )
        {
            k = stri_1[k];
        }
        if(strc_2[k + 1] == strc_2[i])
        {
            k = k + 1;
        }
        stri_1[i] = k;
    }
}

int main()
{
   char strc_1[] = {"bacbababadababacambabacaddababacasdsd"};
   char strc_2[] = {"ababaca"};
   int stri_1[strlen(strc_2)];              //next数组
   int i = 0, j = 0;

   str_next(stri_1, strc_2);

   while(strc_1[i] != '\0')
   {
       while(strc_2[j] != '\0' && strc_1[i] == strc_2[j])   //要是等于就开始循环
       {
           i++;
           j++;
       }
       if(strc_2[j] == '\0')                                //如果都匹配就执行本条语句并跳出
       {
           printf("第%d位之后\n", i - j);
           break;
       }
       j = stri_1[j] + 1;                                   //如遇到不匹配就执行next数组
       i++;

   }
   
   if(strc_1[i] == '\0')
   {
       printf("未在字符串strc_1中找到与字符串strc_2相匹配的项！\n");
   }

    return 0;
}

不弃_

抢沙发