資料結構--串的模式比對算法--BF算法,KMP算法c++

BF算法

算法思路比較簡單,跟KMP比簡直幼稚園級别的,可以指定主串中查找的起始位置,每次比對失敗指針回溯主串指針i=i-j+1,子串指針j=1

#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算法

有點難了解,研究了好長時間才恍然大悟,大概意思找子串每一節的字首和字尾公共串,然後記錄next中,比對的時候通過字首到字尾的滑動,不需要主串的指針回溯

具體解析可以參考這個:https://blog.csdn.net/qq_43656233/article/details/102604833

#include<iostream>
#include<cstring>
using namespace std;
//當k = -1，代表前面比對失敗，重新開始比對。
//當T[k] == T[j]，代表比對成功，進行下一次的比對。
//如果兩個條件都不滿足，讓k = next[k]，去next的位置，重新開始。
//next=前字尾最長公共部分+1
void setNext(string T, int next[])
{
	int tlen = T.length();
	next[0] = -1;
	int j = 0, k = -1;
	while (j < tlen)
	{
		if (k == -1 || T[k] == T[j])
		{
			k++;
			j++;
			next[j] = k;
		}
		else
		{
			k = next[k];
		}
	}
}
int getLocate(string S, string T, int next[])
{
	setNext(T, next);
	int slen = S.length();
	int tlen = T.length();
	int i = 0, j = 0;
	while (i < slen && j < tlen)
	{
		if (j == -1 || S[i] == T[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j == tlen)
	{
		return i - tlen + 1;
	}
	return -1;
}
int main()
{
	int next[100];
	string s = "BBCSABCDABSABCDABCDABDE";
	string t = "ABCDABDABC";
	cout << getLocate(s, t, next);
	return 0;
}