数据结构--串的模式匹配算法--BF算法,KMP算法c++

BF算法

模式匹配可以指定主串中查找的起始位置,算法思路比较简单,每次匹配失败指针回溯主串指针i=i-j+1,子串指针j=1,算法的时间复杂度高O(n*m)

#include <iostream>
using namespace std;
int Index_BF(string A, string B, int pos) {
	int i = pos, j = 0;
	while (i < A.length() && j < B.length()) {
		//两个字符串均为比较到串尾（只有有一个到串尾就跳出循环） 
		if (A[i] == B[j]) {
			i++;
			j++;
		}
		else {
			//匹配失败指针回溯
			i = i - j + 1;
			j = 0;
		}
	}
	if (j >= B.length()) return i - B.length();	
	else return -1;
}
int main() {
	string a = "abckjsef";
	string b = "kjs";
	int flag = Index_BF(a, b, 4);
	if (flag == -1) cout << "子串在主串之中不存在！" << endl;
	else cout << "子串在主串中起始位置为：" << flag + 1 << endl;
	return 0;
}

KMP算法

原文：https://www.cnblogs.com/kongw/p/13972810.html