kmp匹配算法

参考网站

代码

#include 
#include 

using namespace std;

int next[101];

void getNext(string str){ // 获取前缀表部分 
	string tmp = "";
	int cnt = 0;
	next[0] = -1; // 第一个元素对应的前缀为-1 
	for(int i = 0; i < str.length(); i++){
		tmp += str[i]; // 每次加一个元素
		// 把第cnt个元素和最后一个元素对比 
		if(tmp[cnt] != tmp[i]) // 不同时cnt初始化为0  
			cnt = 0;
		if(tmp[cnt] == tmp[i] && i != 0) // 相同时cnt++,用于下一次判断 
			cnt++;
		next[i+1] = cnt; // 每个元素前缀的值为cnt的值 
	}
}

int kmp(string t, string p){ // 字符串比较部分 
	getNext(p);
	int i = 0, j = 0; // i为原文的下标，j为需要匹配的字符串下标 
	while(i < t.length() && j < p.length()){ // 边界 
		if(j == 0 || t[i] == p[j]){ // 当前前缀的值为0或者两个元素相等时，继续 
			i++;
			j++;
		}
		else // 匹配失败，根据前缀表继续跳转 
			j = next[j];
	}
	if(j == p.length()) // 当全部匹配时返回 
		return i - j; // 返回匹配到的位置 
	return -1; 
}

int main(){
	string t = "bbc abcdab abcdabcdabde";
	string p = "abcdabd";
	cout << kmp(t, p) << endl; 
}