政务信息网站建设工作方案app推广注册放单平台

       BF算法匹配过程易理解，若匹配，子串和主串都往下移一位。不匹配时，主串回溯至本次匹配开始下标的下一位。例：图中第三趟匹配时，主串到第七位时与子串不匹配，这次匹配主串是从第三位开始的，所以下次要从第四位开始（i-j+2=7-5+2=4）。

#include<iostream>
#include<string>
using namespace std;
typedef struct node
{char ch[251];int length=0;//串当前长度
}SString;
int Index_BF(SString S, SString T, int pos)//S主串，T子串，pos从主串pos位置开始匹配
{int i = pos, j = 1;//i为主串下标，j为子串下标while (i <= S.length && j <= T.length){if (S.ch[i] == T.ch[j])//匹配，往下继续{i++;j++;}else{i = i - j + 2;//不匹配，主串回溯至本次匹配开始下标的下一位j = 1;//子串重新开始}}if (j >= T.length) return i - T.length;//返回主串与子串匹配时，主串的第一个下标else return 0;}
int main()
{SString  s;SString  t;cout << "输入主串长度：" ;cin >> s.length;cout << endl;cout << "输入子串长度：";cin >> t.length;cout << endl << "输入主串：";for (int i = 1; i <= s.length; i++)//从下标1开始储存{cin >> s.ch[i];}cout << endl << "输入子串：";for (int i = 1; i <= t.length; i++){cin >> t.ch[i];}int a = Index_BF(s, t, 1);cout <<endl<< a;
}