KMP算法原理与实现（精简） - c++编程基础

思想：使源字符串中的下标不回溯，利用模式字符串自身的相关性，减少模式字符串中下标回溯的距离。从而减少比较的次数。

关键问题：分析模式字符串，得出部分匹配值数组。

原理参考此处。

具体实现：

#include 
  
   
#include 
   
     #include 
    
      void get_next(int next[], char source[], int n);//获取部分匹配字符数组 int Index_KMP(char* s_string, char* t_string, int pos);//返回源字符串s_string中pos开始 与t_string匹配的第一个字符串首字母下标，无匹配返回0 int main() { char *source_str = "BBC ABCDAB ABCDABCDABDE"; char *t_str = "ABCDAB";//模式串 printf("%d\n", Index_KMP(source_str, t_str, 8)); return 0; } void get_next(int next[], char source[], int n) { int i = 0; next[0] = 0; for(i = 1; i < n; i++) { if(source[i] == source[next[i-1]]) next[i] = next[i-1] + 1; else next[i] = 0; } } int Index_KMP(char* s_string, char* t_string, int pos) { int i = pos;//指向 s_string的起始下标 int j = 0;//指向 t_string的起始下标 int t_len = strlen(t_string); int s_len = strlen(s_string); int* t_next = (int*)malloc(sizeof(int)*t_len); int m; get_next(t_next, t_string, t_len);//获取t_string的部分匹配字符数组 for(m = 0; m < t_len; m++) printf("%d ",t_next[m]); printf("\n"); while( (i