串的模式匹配算法——BF算法及其复杂度
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
版权声明：本文为博主原创文章，转载请附上博文链接！