字符串匹配算法非常常见，也非常实用。比如我们常在IDE中查找字符串，比如我们做关键词匹配，都需要进行字符串查找，底层是怎么实现的那，先介绍两种最简单的字符串匹配算法：BF算法和RK算法。

一BF匹配算法

BF匹配算法，即Brute-Force算法的简称，其实就是我们自己可以想到的最简单的算法。在介绍这个算法之前，先来了解什么是模式串，什么是主串。在字符串匹配算法中，如果需要在字符串A中查找字符串C，那么字符串A就是主串，C字符串称为模式串。 假设主串的长度为n，模式串的长度为m，m小于等于n。 BF算法的逻辑就是依次从主串中0，1，2....n-m的位置，一一比较模式串和主串的字符是否相同，如果模式串都匹配完了均相同，则匹配，负责继续向后匹配。 借老师的一张图来表示很明确：

用java代码实现下：

public class BFSearch {    public static int search(String mainStr,String modeStr)    {        int n = mainStr.length();        int m = modeStr.length();        if (n < m) {            return -1;        }        char [] a = mainStr.toCharArray();        char [] b = modeStr.toCharArray();        int j = 0;        int i = 0;        int k = 0;        for ( i = 0; i <= n-m; i++ ) {            k = i;            for (j = 0; j < m;j++) {                if (a[k] == b[j]) {                    k++;                } else {                   break;                }            }            if (j == m ) {                return i;            }        }        return -1;    }    public static void main(String [] args) {        String main_str = "abcdef";        String mode_str = "abc";        System.out.println(BFSearch.search(main_str,mode_str));    }}

本来以为是最简单的字符串匹配算法，竟然写的时候发现几个bug，真是绝知此事要躬行啊! 通过代码分析来看，算法复杂度为O( (n-m)m) 约等于O（nm)。 虽然复杂度很高，但是用的还挺多，原因：

理论上看起来算法复杂度比较高，但是，每次匹配不一定是m，如果不匹配则直接进入下一轮循环了。实现起来比其他算法要简单。

##RK算法 RK算法全称Rabin-Karp算法，可以看作是BF算法的升级，BF算法的时候我们对n-m+1个长度为m的子串进行依次匹配，RK算法是对n-m+1个字串求hash值，对模式串求hash值，然后进行比较，如果hash不一样，那么肯定两个字符串不一样，如果hash值一样，则进行进一步匹配，当然如果是不冲突的hash算法也可以只通过hash值比较。

整体来说hash计算需要时间，比较上来说减少了字符串的比较，但是到底性能是不是一定比BF算法要好，我觉得不一定，这就要求算法设计上有一定的技巧，王争老师提供了一个很好的hash算法，假如我们所有的字符串只有小写字母组成，那么我们可以把一个字符串看作是26进制的数字，然后计算出每个子串的hash值，且hash值是有规律的，可以简化计算，举例下：

hash("abc") = 'a' *26*26 + 'b'*26+'c' = 0*26*26 + 1*26 +2 = 28

如上的话，假如模式串长度为三，则计算hash的情况如下：

如果按照上面26进制的方法： hash(dbc) = 3*26*26+ 1*26+2 hash(bce) = 1*26*26 +2*26+4

看看图片：

不过以上计算方法虽然不存在算法冲突的问题，但是，如果字符串太长，则容易出现溢出。 可以用其他hash算法替代。

还可以优化的地方是像26的n次方可以直接保存在一个数组中，不需要计算直接查询即可。 另外在实际的代码中，可以先计算模式串，计算出一个主串的子串就进行比较，如果匹配就直接返回， 如果不匹配，再计算下一个字串。RK算法优化的好的话，性能和KMP算法的是相同数量级的，很接近。

具体实现可以参考 RK算法的python实现