BF字符串匹配(C++)

C++版本

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

int BF(string s,string t)
{
	int i=0,j=0;
	while(i<s.size() && j<t.size())
	{
		if(s[i] == t[j])
		{
			i++,j++;
		} else {
			i = i-j+1;
			j = 0;
		}
	}
	
	return (j>=t.size())? (i-t.size()):-1;
}

int main()
{
	string x,y;
	
	cin>>x>>y;
	
	int cnt = BF(x,y);
	
	if(cnt == -1)
		cout<<"匹配失败!"<<endl;
	else
		cout<<"匹配成功 下标为"<<cnt<<endl;
	return 0;
}

C版本

#include<iostream>
#include<string.h>
using namespace std;

//BF算法函数
int BF(char*S, char*T)
{
	//主串的长度
	int lenS = strlen(S);
	//子串的长度
	int lenT = strlen(T);
	//定义i，j分别作为主串和子串的指示器
	int i = 0, j = 0;
	//当主串和子串没有匹配完全时执行该while语句
	while (i < lenS && j < lenT)
	{
		//如果此时主串和子串的元素匹配成功
		if (S[i] == T[j])
		{
			//就让它们指向后一个元素继续进行匹配操作
			i++;
			j++;
		}
		//如果匹配不成功的话就要进行回溯操作
		//主串回溯。子串的j指向0
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	//如果此时j的值大于等于子串的长度说明已经匹配成功
	if (j >= lenT)
	{
		//返回匹配成功的位置
		//因为我们此时是从下标0开始的
		//所以我们往后加了一个1返回的是子串在主串中的位置
		return i - lenT + 1;
	}
	//匹配不成功
	else
	{
		return -1;
	}
	
}

int main()
{
	char S[100], T[100];
	while (1)
	{
		cout << "请输入主串" << endl;
		cin >> S;
		cout << "请输入子串" << endl;
		cin >> T;
		int ret = BF(S, T);
		if (ret == -1)
		{
			cout << "很抱歉，匹配失败，未在主串中找到子串的相关信息" << endl;
		}
		else
		{
			cout << "匹配成功" << endl << "匹配成功的位置为" << ret << endl;
		}
	}
	return 0;
}