串是由零个或多个字符组成的有限序列，又叫做字符串
串的逻辑结构和线性表很相似的，不同的是串针对是是字符集，所以在操作上与线性表还是有很大区别的。线性表更关注的是单个元素的操作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; while (i < sourcestr.length) { // 两字母相等则继续 if (sourcestr.charat(i) == searchstr.charat(j)) { i++; j++; } else { // 两字母不等则角标后退重新开始匹配 i = i - j + 1; // i 回退到上次匹配首位的下一位 j = 0; // j 回退到子串的首位 } if (j == searchstr.length) { return i - j; } }}
i就是主串的下标定位，j就是子串的下标定位
当主串子串相等的时候，就进入了子串的循环模式，当子循环的次数j满足子串长度时，就验证是完全匹配
当主串子串不相等的时候，就需要把主串的下标往后移一位，当然i的时候，因为可能经过子串的处理，所以需要i-j+1, 然后复位子串
具体我们可以看看代码比较
基于bf算法的四种结构,for/while/递归
由于电脑性能的不断提高，测试的数据量的大小，可能会导致得到的结果不太准确;
bf也是经典的前缀匹配算法，前缀还包括kmp，我们可见这种算法最大缺点就是字符匹配失败指针就要回溯，所以性能很低，之后会写一下kmp与bm算法针对bf的的升级
git代码下载: https://github.com/jsaaron/data_structure