数据结构与算法JavaScript (四) ：串(BF)

455 查看

串是由零个或多个字符组成的有限序列，又叫做字符串

串的逻辑结构和线性表很相似的，不同的是串针对是是字符集，所以在操作上与线性表还是有很大区别的。线性表更关注的是单个元素的操作CURD，串则是关注查找子串的位置，替换等操作。

当然不同的高级语言对串的基本操作都有不同的定义方法，但是总的来说操作的本质都是相似的。比如javascrript查找就是indexOf, 去空白就是trim,转化大小写toLowerCase/toUpperCase等等

这里主要讨论下字符串模式匹配的几种经典的算法：BF、BM、KMP

BF(Brute Force)算法

Brute-Force算法的基本思想：

从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。

依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功

可见BF算法是一种暴力算法，又称为朴素匹配算法或蛮力算法。

主串 BBC ABB ABCF

子串 ABC

在主串中找出子串的位置，对应了其实就是javascript的indexOf查找方法的实现了

var sourceStr = "BBC ABB ABCF";

var searchStr = "ABC";

function BF_Ordinary(sourceStr, searchStr) {

var sourceLength = sourceStr.length;

var searchLength = searchStr.length;

var padding = sourceLength - searchLength; //循环的次数

//BBC ABB ABCF =>ABC => 搜索9次

for (var i = 0; i <= padding; i++) {

//如果满足了第一个charAt是相等的

//开始子循环检测

//其中sourceStr的取值是需要叠加i的值

if (sourceStr.charAt(i) == searchStr.charAt(0)) {

//匹配成功的数据

var complete = searchLength;

for (var j = 0; j < searchLength; j++) {

if (sourceStr.charAt(i + j) == searchStr.charAt(j)) {

--complete

if (!complete) {

return i;

}

return -1;

}

BF算法就是简单粗暴，直接把BBC ABB ABCF母串的每一个字符的下表取出来与模式串的第一个字符匹配，如果相等就进去字串的再次匹配

这里值得注意：

1：最外围循环的次数sourceLength – searchLength，因为我们匹配的母串至少要大于等于子串

2：在子串的继续匹配中，母串的起点是需要叠加的(i+j)

3：通过一个条件判断是否完全匹配complete，BBC ABB ABCF中，我们在ABB的时候就需要跳过去

上面是最简单的一个算法了，代码上还有更优的处理，比如在自串的匹配上可以采取取反的算法

优化算法（一）

function BF_Optimize(sourceStr, searchStr) {

var mainLength = sourceStr.length;

var searchLength = searchStr.length;

var padding = mainLength - searchLength;

for (var offset = 0; offset <= padding; offset++) {

var match = true;

for (var i = 0; i < searchLength; i++) {

//取反,如果只要不相等

if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {

match = false;

break;

}

if (match) return offset;

}

return -1;

}

我们不需要判断为真的情况，我们只要判断为假的情况就可以了，当子匹配结束后match没有被修改过的话，则说明此匹配是完全匹配

以上2种方法我们都用到了子循环，我们能否改成一个循环体呢？

其实我们可以看到规律，主串每次都只会递增+1，子串每次匹配也是从头开始匹配，所以我们可以改成一个while，控制下标指针就可以了

优化算法（二）

function BF_Optimize_2(sourceStr, searchStr) {

var i = 0,

j = 0;an class="crayon-o">= 0,

j = 0;܉不同的定义方法，但是总的来说操作的本质都是相似的。比如javascrript查找就是indexOf, 去空白就是trim,转化大小写toLowerCase/toUpperCase等等

这里主要讨论下字符串模式匹配的几种经典的算法：BF、BM、KMP

BF(Brute Force)算法

Brute-Force算法的基本思想：

从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。

可见BF算法是一种暴力算法，又称为朴素匹配算法或蛮力算法。

主串 BBC ABB ABCF

子串 ABC

在主串中找出子串的位置，对应了其实就是javascript的indexOf查找方法的实现了

var sourceStr = "BBC ABB ABCF";

var searchStr = "ABC";

function BF_Ordinary(sourceStr, searchStr) {

var sourceLength = sourceStr.length;

var searchLength = searchStr.length;

var padding = sourceLength - searchLength; //循环的次数

//BBC ABB ABCF =>ABC => 搜索9次

for (var i = 0; i <= padding; i++) {

//如果满足了第一个charAt是相等的

//开始子循环检测

//其中sourceStr的取值是需要叠加i的值

if (sourceStr.charAt(i) == searchStr.charAt(0)) {

//匹配成功的数据

var complete = searchLength;

for (var j = 0; j < searchLength; j++) {

if (sourceStr.charAt(i + j) == searchStr.charAt(j)) {

--complete

if (!complete) {

return i;

}

return -1;

}

BF算法就是简单粗暴，直接把BBC ABB ABCF母串的每一个字符的下表取出来与模式串的第一个字符匹配，如果相等就进去字串的再次匹配

这里值得注意：

1：最外围循环的次数sourceLength – searchLength，因为我们匹配的母串至少要大于等于子串

2：在子串的继续匹配中，母串的起点是需要叠加的(i+j)

3：通过一个条件判断是否完全匹配complete，BBC ABB ABCF中，我们在ABB的时候就需要跳过去

上面是最简单的一个算法了，代码上还有更优的处理，比如在自串的匹配上可以采取取反的算法

优化算法（一）

function BF_Optimize(sourceStr, searchStr) {

var mainLength = sourceStr.length;

var searchLength = searchStr.length;

var padding = mainLength - searchLength;

for (var offset = 0; offset <= padding; offset++) {

var match = true;

for (var i = 0; i < searchLength; i++) {

//取反,如果只要不相等

if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {

match = false;

break;

}

if (match) return offset;

}

return -1;

}

我们不需要判断为真的情况，我们只要判断为假的情况就可以了，当子匹配结束后match没有被修改过的话，则说明此匹配是完全匹配

以上2种方法我们都用到了子循环，我们能否改成一个循环体呢？

其实我们可以看到规律，主串每次都只会递增+1，子串每次匹配也是从头开始匹配，所以我们可以改成一个while，控制下标指针就可以了

优化算法（二）

function BF_Optimize_2(sourceStr, searchStr