串的模式匹配算法——BF算法（C++代码）
⽂章⽬录
⼦串的定位操作通常称作串的 匹配模式（其中P,T称为模式串，PaTtern），是各种串处理系统中最重要的操作之⼀。
在串的模式匹配中， ⼦串P称为模式，主串S称为⽬标。
⽰例：
⽬标S："Beijing"
模式P："jin"
匹配结果=3(匹配位置从0开始)
Brute—Force 简称BF算法，亦称简单匹配算法。采⽤穷举的思想。
⼀. 具体思路
1. 初始时让⽬标 S 的第 0 位与模式 P 的第 0 位对齐；
2. 顺序⽐对⽬标 S 与模式 P 中的对应字符：
①. 若 P 与 S ⽐对发现对应位不匹配，则本趟失配。将 P 右移⼀位与 S 对齐，进⾏下⼀趟⽐对；
②. 若 P 与 S 对应位都相等，则匹配成功，返回 S 当前⽐较指针停留位置减去 P 的长度，即⽬标 S 中匹配成功的位置，算法结束；
③ 若 P 与 S ⽐对过程中， S 后⾯所剩字符个数少于 P 的长度，则模式匹配失败。
⼆. C++代码实现
#include<iostream>
#include<string>
using namespace std;
int index(string &S, string &P,int pos)
{//pos是从指定位置开始进⾏匹配
int i = pos, j =0;
//i代表主串当前待⽐较的位置，j代表⼦串当前待⽐较的位置
while(i<S.size()&& j<P.size())
{
if(S[i]== P[j])
{
i++;//若当前字符相同，则继续向下⽐较
j++;
}
el//主串，⼦串指针回溯重新开始下⼀次匹配
{
i=i-j+1;//主串退回到开始匹配
j=0;//⼦串从头开始匹配
}
}
if(j>=P.size())
return(i-P.size());//返回匹配的第⼀个字符的下标
el
return-1;// 模式匹配不成功
}
int main()
{
string S,P;
int pos;
cin >> S >> P >> pos;
int x=index(S,P,pos);
if(x==-1)
cout <<" 匹配不成功"<< endl;
el
cout <<"匹配成功"<<"匹配结果=x"<< endl;
return0;
}
运⾏结果为：
三. BF算法分析
若设n为⽬标S的长度，m是模式P的长度，匹配算法最多⽐较n-m+1趟。若每趟⽐较都⽐较到模式P尾部才出现不等，要做m此⽐较，则在最坏的情况下，总⽐较次数（n-m+1）m。在多数场合下，m远⼩
于n因此，==算法的运⾏时间为O（n m）==。
四. 低效的原因
算法在字符⽐较不相等，需要回溯（即i=i-j+1）：即退到S中的下⼀个字符开始进⾏继续匹配。
五. 参考
中国⼤学MOOC 《数据结构》青岛⼤学 刘遵仁
