5_25打卡_字符串暴力匹配和kmp匹配-526互联

#include<iostream>
#include<vector>
#include<string>
using namespace std;

//暴力匹配
void force_match(string& a, string& b)
{
	int i = 0, j = 0;
	while (i < a.size() && j < b.size())
	{
		if (a[i] == b[j])
		{
			i++;
			j++;
		}
		else {
			i = i - j + 1;
			j = 0;
		}
	}
	if (j >= b.size())
	{
		cout << "force匹配成功" << endl;
	}
	else {
		cout << "force匹配失败" << endl;
	}
}


//kmp匹配
//生成next数组
vector<int> build_next(string& a)
{
	vector<int> b;
	b.push_back(0);//第一项共同前后缀长度为0
	int i = 1;
	int len = 0;//共同前后缀长度  //len的长度等于前后缀的长度 （即上一位(相较于i，即i-1位，在循环过程中i走在len前)元素的共同前后缀大小）
	while (i < a.size())
	{
		//相等时
		if (a[i] == a[b[len]])
		{
			i++;
			len++;
			b.push_back(len);
		}
		//不相等时
		else {
			if (len > 0)
			{
				len = b[len - 1];//将len（即上一位(i-1位)的共同前后缀大小）更新到第len个元素的len（即第len个元素上一位元素的共同前后缀大小）
			}
			else {
				i++;
				len = 0;
				b.push_back(0);
			}
		}
	}
	return b;
}

void kmp_match(string& c,string& a)
{
	vector<int> b = build_next(a);
	int i = 0, j = 0;//i指向a,j指向c，c为查找源，a为查找目标
	while (i < a.size() && j < c.size())
	{
		if (a[i] == c[j])
		{
			i++;
			j++;
		}
		else {
			if (i > 0)
			{
				i = b[i - 1];//如果i>0,则比较a[i-1]（i-1的len（len为共同前后缀长度））与c[j]
			}
			else {
				i = 0;
				j++;
			}
		}
	}
	if (i >= a.size())
	{
		cout << "kmp匹配成功" << endl;
	}
	else {
		cout << "kmp匹配失败" << endl;
	}
}

int main()
{
	string a = "aksjhf";
	string b = "aksjh";
	kmp_match(a, b);
	force_match(a, b);
	a = "alkfhalkfhlgaaaskjfg";
	b = "kfhh";
	kmp_match(a, b);
	force_match(a, b);
	b = "alk";
	kmp_match(a, b);
	force_match(a, b);
	b = "aas";
	kmp_match(a, b);
	force_match(a, b);
	return 0;
}