BF 算法总感觉写法怪怪的，改了一下

ZhaoYuBetter

欢迎拍砖哈，代码个数 可使用 codeblok 格式化一下：算法学起来比较吃力。。。:cry

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef char* String;
   
5. 
   
6. // 返回子串T在主串S中第pos个字符之后的位置
   
7. // 若不存在，则返回0
   
8. // T非空，1 <= pos <= strlen(S)
   
9. int index(String S, String T, int pos)
   
10. {
    
11.       int i = pos;
    
12.       int j = 0;
    
13.       int lenS = strlen(S);
    
14.       int lenT = strlen(T);
    
15. 
    
16.      while(i<lenS && j<lenT) {
    
17.       if(S[i] == T[j]) {      // 判断下一个
    
18.          i++;
    
19.           j++;
    
20.      } else {        // 回溯
    
21.         i = i-j+1;
    
22.         j = 0;
    
23.      }
    
24.     }
    
25. 
    
26.     if(j > lenT - 1) {
    
27.     return i - lenT;
    
28.     } else {
    
29.     return -1;
    
30. }
    
31. }
    
32. 
    
33. int main()
    
34. {
    
35.     int i;
    
36.     i = index("Helloo", "lo", 0);
    
37.     printf("index: %d", i);
    
38.     return 0;
    
39. }
    

复制代码

ZhaoYuBetter

一般编程语言，都是 返回 -1 表示匹配不到的意思。

ZhaoYuBetter

修改好的 KMP 算法：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef char* String;
   
5. 
   
6. 
   
7. // KMP 算法start
   
8. /*
   
9. 获取 KMP 的 next 数组
   
10. */
    
11. void getNext(String T, int *next)
    
12. {
    
13.     int j = -1;  // 前
    
14.     int i = 0;  // 后
    
15. 
    
16.     next[0] = -1;            // next数组第一个元素为-1
    
17.     int lenT = strlen(T);   // 字符串长度
    
18. 
    
19.     while( i < lenT)
    
20.     {
    
21.         // 刚开始or匹配相等加1向前走（BF原則）
    
22.         if(-1==j || T[i] == T[j])
    
23.         {
    
24.             j++;
    
25.             i++;
    
26.             if(T[i] != T[j])
    
27.             {
    
28.                 next[i] = j;    // 填下一个
    
29.             }
    
30.             else
    
31.             {
    
32.                 next[i] = next[j];
    
33.             }
    
34. 
    
35.         }
    
36.         else
    
37.         {
    
38.             j = next[j];
    
39.         }
    
40.     }
    
41. }
    
42. 
    
43. // 返回子串T在主串S第pos个字符之后的位置
    
44. // 若存在，返回-1
    
45. int indexKMP(String S, String T, int pos)
    
46. {
    
47.     int i = pos;
    
48.     int j = 0;
    
49.     int next[255];
    
50. 
    
51.     getNext(T, next);   // 获取next数组
    
52.     int lenS = strlen(S);
    
53.     int lenT = strlen(T);
    
54. 
    
55.     while(i<lenS && j<lenT)
    
56.     {
    
57.         if(-1 == j || S[i] == T[j]) //j=-1，没有这个元素，指向下一个元素，类似BF算法
    
58.         {
    
59.             i++;
    
60.             j++;
    
61.         }
    
62.         else            // 匹配失败
    
63.         {
    
64.             j = next[j];
    
65.         }
    
66.     }
    
67. 
    
68.     if(j > lenT - 1)
    
69.     {
    
70.         return i - lenT;
    
71.     }
    
72.     else
    
73.     {
    
74.         return -1;
    
75.     }
    
76. 
    
77. 
    
78. }
    
79. 
    
80. 
    
81. // KMP 算法end
    
82. 
    
83. int main()
    
84. {
    
85. 
    
86.     i =  indexKMP("ababaaabacca", "aaaa", 0);
    
87.     printf("KMP, index: %d ", i);
    
88.     printf("\n");
    
89.     return 0;
    
90. }
    

复制代码

磨牙耗子

4#说的啥、