【数据结构与算法】BF算法（详解）

您所在的位置：网站首页 › 数据结构与算法串实验总结 › 【数据结构与算法】BF算法（详解）

【数据结构与算法】BF算法（详解）

2024-07-10 15:36| 来源: 网络整理| 查看: 265

目录（一）BF算法（二）演示（三）时间复杂度（四）代码实现

我的KMP算法点我（一）BF算法

也就是串的模式匹配算法，在主串中查找与模式T（副串）相匹配的子串，如果匹配成功，找到该子串在主串出现的第一个字符。模式匹配不一定是从主串第一个字符开始，可以在主串中指定起始位置。

（二）演示

举个例子：主串：我是大明我我是小明嘿嘿嘿模式串：我是小明

现在我们要在主串中找到符合模式串的连续字符。下面是匹配过程描述：

假设 i 从0开始，j 初始都为0，当 S[i]==T[j] 时，i++，j++，当 S[i]!=[j] 时，i返回起始值再加一，j回到0。

第一趟匹配：起始值i=0,j=0

i=2 我是大明我我是小明嘿嘿嘿 j=2 我是小明

“大”和“小”不匹配。i变为0再加1，“是”字符的下标。j变为0

i=1 我是大明我我是小明嘿嘿嘿 j=0 我是小明

第二趟匹配： S[i]!=T[j],一直执行i返回起始值再加一，j回到0，直到S[i]==T[j] S[2]!=T[0]，S[3]!=T[0]，S[4]==T[0]

i=4 我是大明我我是小明嘿嘿嘿 j=0 我是小明

S[i]==T[j]，i++,j++

i=5 我是大明我我是小明嘿嘿嘿 j=1 我是小明

又不匹配了。

第三趟匹配： i回到起始值再加一 i=5，j=0

i=5 我是大明我我是小明嘿嘿嘿 j=0 我是小明

S[i]==T[j]，i++,j++

i=8 我是大明我我是小明嘿嘿嘿 j=3 我是小明

匹配成功，返回i的起始值（i-T.length）。

（三）时间复杂度

设主串长度为n，模式串长度为m，假设主串从第 i 个位置与模式串匹配成功，则此前 i-1 趟字符总比较了 i-1 次，第i趟成功比较字符次数为m，则总比较次数为 i-1+m 次。对于成功匹配的主串，其起始位置由 1 到 n-m+1，假定这 n-m+1 个起始位置上的匹配概率相等，则最好的情况下匹配成功的平均比较次数为：在这里插入图片描述所以最好情况下平均时间复杂度是O(n+m) 最坏情况是每次匹配不成功发生在模式串最后一个字符，直达主串最后一个字符与之匹配。复杂度为： O(n*m)

（四）代码实现 public int IndexOfBF(String S,String T,int pos){ char []a = S.toCharArray(); char []b = T.toCharArray(); int i=pos;int j=0; while(i

【本文地址】

【数据结构与算法】BF算法（详解）

【数据结构与算法】BF算法（详解）

今日新闻

推荐新闻