[数据结构与算法]C++版模式匹配BF算法

有两个字符串，找到子串在父串中的位置，返回子串在父串中的第一个字符下标：

? ? 1、定义两个变量i和j，分别作为在父串和子串中要比对字符的下标；

? ? 2、设置while循环，条件为i和j都不能超出各自字符串的尺寸；

? ? 3、循环中，从0位置开始依次比对元素，若父串中i位置上的元素的值==子串j位置上的元素的值：j++；i++；。若不等于，i回退到i - j + 1、j回退到0。

? ? 4、循环完毕后，匹配成功的标志是j等于子串的长度，成功后，子串在父串首次出现的下标为i减去子串的长度。

代码实现：

? ??

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

string father, son;

int main()
{
    cout << "请输入主串" << endl;
    cin >> father;
    cout << "请输入子串" << endl;
    cin >> son;
    int f_size = father.size();
    int s_size = son.size();
    cout << father << endl;
    cout << son << endl;
    int i = 0, j = 0;    //两个串的要比对元素的下标
    while (i < f_size && j < s_size)    //条件为i、j均不超界
    {
        if (father[i] == son[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j < s_size)     
    {
        cout << "没有找到子串" << endl;
    }
    else
    {
        cout << "子串在第：" << i - s_size << "个位置" << endl;
    }

    return 0;
}