KMP算法

奥普瓯江

原理：

备注：

代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. void str_next(int stri_1[], char strc_2[]);
   
6. void str_next(int stri_1[], char strc_2[])
   
7. {
   
8.     stri_1[0] = -1;
   
9.     int k = -1;
   
10. 
    
11.     for(int i = 1; i < strlen(strc_2); i++)
    
12.     {
    
13.         while(k > -1 && strc_2[k + 1] != strc_2[i] )
    
14.         {
    
15.             k = stri_1[k];
    
16.         }
    
17.         if(strc_2[k + 1] == strc_2[i])
    
18.         {
    
19.             k = k + 1;
    
20.         }
    
21.         stri_1[i] = k;
    
22.     }
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.    char strc_1[] = {"bacbababadababacambabacaddababacasdsd"};
    
28.    char strc_2[] = {"ababaca"};
    
29.    int stri_1[strlen(strc_2)];              //next数组
    
30.    int i = 0, j = 0;
    
31. 
    
32.    str_next(stri_1, strc_2);
    
33. 
    
34.    while(strc_1[i] != '\0')
    
35.    {
    
36.        while(strc_2[j] != '\0' && strc_1[i] == strc_2[j])   //要是等于就开始循环
    
37.        {
    
38.            i++;
    
39.            j++;
    
40.        }
    
41.        if(strc_2[j] == '\0')                                //如果都匹配就执行本条语句并跳出
    
42.        {
    
43.            printf("第%d位之后\n", i - j);
    
44.            break;
    
45.        }
    
46.        j = stri_1[j] + 1;                                   //如遇到不匹配就执行next数组
    
47.        i++;
    
48. 
    
49.    }
    
50.    
    
51.    if(strc_1[i] == '\0')
    
52.    {
    
53.        printf("未在字符串strc_1中找到与字符串strc_2相匹配的项！\n");
    
54.    }
    
55. 
    
56.     return 0;
    
57. }
    

复制代码

不弃_

抢沙发