字符串搜索(查找)概述

字符串查找也叫字符串搜索或字符串匹配，就是从一段文本中查找一小段文本，返回完整匹配的位置。字符串查找的算法有很多种，如：Boyer-Moore算法、Rabin-Karp算法、KMP算法等。最好理解的是朴素搜索法，也就是穷举比较，其算法复杂度接近于：O(N * M)。这里以朴素搜索为例来引入门。

步骤是：

1. 建立两个循环，外循环是被查找的文本，内循环是查找字符串；

2. 将查找字符串逐个与被查找的文本对比，当遇到有不相等时，跳出内循环，文本指针向后移动一位，从下一个开始比较；

如果内循环遍历完成后，还没有不相等的情况，则表示匹配成功，返回当时文本内容的下标，否则返回-1。

朴素算法执行过程分析：朴素搜索算法代码实现：

function find(str, content) {

var i, conetentLen = content.length

var j, strLen = str.length

// 两个循环，外层是被查找文本，内循环是查找字符串

for (i = 0; i < conetentLen; i++) {

for (j = 0; j < strLen; j++) {

// 当遇到不有不相等时，跳出从文本下一个字符开始比较

if (str[j] !== content[i + j]) {

break

}

}

// 如果查找字符串全部比较完成表示成功匹配

if (j === strLen) {

return i

}

}

// 如果文本全部比较完还是没有查找到，则返回-1

return -1

}

find('ABC', 'ABABC') // 2

find('AAB', 'AAABC') // 1

find('ABC', 'AABAC') // -1