S串為主串，T為待比對串，用i、j分别訓示S和T中的字元位置，i、j初值均為0。
算法步驟：（1）若目前比較的字元是s【i】==T【j】，則繼續向後比較，執行（i++，j++）；
（2）若目前正在比較的字元不比對呢？那麼j回溯到位置0（即令j=0），i呢？回溯到主串的i-j+1處
0 1 2 3 4 5 6 7
a b a b c a b d i=2
a b d j=2
a b d j=2；i=7（比對完成） j=3；i=8
（3）如何判定什麼時候能繼續比較，什麼時候比對完成呢？
顯然，比對操作要求S串和T串都沒到串尾，用語句（i
#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
int BF_match(string &s1, string &s2) //"BF算法"
{
int i = 0, j = 0;
int N1 = s1.size(), N2 = s2.size();
while (i <N1&&j < N2)
{
if (s1[i] == s2[j])
{
i++;
j++;
}
else
{
i = i - j + 1;
j = 0;
}
}
if (j >= N2) return (i-N2+1);
return 0;
}
void main()
{
string s1, s2;
cin >> s1;
cin >> s2;
int p;
p = BF_match(s1, s2);
cout << p;
system("pause");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
設S長n，T長m
最好時間複雜度：
最好情況下，在主串第i個位置比對成功，最好情況下前i-1次每次第一次比對就失配，前i-1趟比較i-1次，總共進行i-1+m次比較，i可以是從位置1到n-m+1的任何位置：
1/（n-m+1）∑i-1+m=1/2（n+m）
最壞時間複雜度：
最壞情況下，前i-1次每次比較m次才确定失配，前i-1次共比較（i-1）*m，總共比較（i-1）*m+m次，
1/（n-m+1）∑i*m=1/2m*（n-m+2）
用BF算法，每次比對不成功，主串都要回到i-j+1位置處重新比較，可顯然這個回溯操作可以跳過，S與T失配前的i-j——i位與T的前j-1位相同，那麼通過T自己比對自己，我們能否知道S和T比對過程中可以跳幾位呢？
---------------------
作者：weixin_41338006
來源：CSDN
原文：https://blog.csdn.net/weixin_41338006/article/details/78930547
版權聲明：本文為部落客原創文章，轉載請附上博文連結！