本文共 1182 字，大约阅读时间需要 3 分钟。

KMP算法的核心: 避免了指针的回溯

1. 寻找子串和主串第一个相同的字符

此时的特点：当前字符以前，子串与主串全部相同。

2. 判断当前位置以前，子串的前溯和后溯的最大重叠子串

要求: 1. 最大重叠 2. 为真回溯(即不包含原串)

3. 移动子串

即对重叠子串进行操作

代码如下:

# include 
   
    # include 
    
     # include 
     
      # include 
      
       # include 
       
        using namespace std;// KMP算法的核心是避免指针的回溯 // 当两个字符不匹配时, 寻找最大公共前后缀 void getNext(int next[], string t) {
   	int j = 0, k = -1;	next[0] = -1;		while(j < t.length() - 1) {
   		if(k == -1 || t[j] == t[k]) {
   			j++, k++;//			if(t[++j] == t[++k]) {	// 当两个字符相等时要跳过 //				next[j] = next[k];//			}//			else {
   //				next[j] = k;//			}			next[++j] = ++k;		}		else {
   			k = next[k];		}	}}int KMP(string s, string t) {
   	int next[t.length()];	int i = 0;	// 主串的位置 	int j = 0;	// 模式串的位置 	getNext(next, t);		// 此处需要用int转化, 否则只经过一次循环, 原因未知	while(i < (int)s.length() && j < (int)t.length()) {
   		if(j == -1 || s[i] == t[j]) {
   			// 当j=-1时, 要移动i, j归零 			i++;			j++;		}		else {
   			// i = i - j + 1;	i不需要回溯 			j = next[j];	// j回退 		}	}	return (j >= t.length()) ? (i - j) : (-1);}int main(void) {
   	string a = "abcabcbhijk";	string b = "bcb";		cout << KMP(a, b) << endl;		system("pause");	return 0;}
       
      
     
    
   

输出结果:

参考文章:

转载地址：http://evlqf.baihongyu.com/