字符串匹配：BF&RK

BF算法

Brute Force算法，暴力匹配算法，也叫朴素匹配算法。

在字符串A中查找字符串B，字符串A为主串，字符串B为模式串。主串的长度记为n，模式串的长度记作m，主串中查找模式串，n>m。

算法思想：
在主串中，检查起始位置分别是0、1、2…n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。

BF算法

/**
* @param main 主串
* @param pattern 模式串
* @return 匹配下标的起始值
*/
public int indexBf(char[] main,char[] pattern) {
    //最大的首个字符的索引
    int maxFirst = main.length -pattern.length;
    char first = pattern[0];
    for(int i = 0; i <= maxFirst; i++) {
        //第一个匹配的字符
        while(first != main[i]) {
            if(++i > maxFirst) 
                return -1;
        }
        //子串匹配
        int m = i+1;
        for(int j = 1; j < pattern.length; j++,m++) {
            if(main[m] != pattern[j])
                break;
        }
        //匹配成功
        if(m -i == pattern.length)
            return i;
    }
    retuen -1;
}

时间复杂度：
极端情况下，在“aaaa…aaaa”中查找“aaaab”。每次都对比m个字符，要对比n-m+1次，最坏情况时间复杂度是O(n*m)。

1. 实际软件开发中，模式串和主串长度不会太长，每次模式串与主串中的子串匹配时，中途遇到不能匹配的字符的时候就可以停止，不需要把每个字符都比对一下。
2. 算法思想简单，代码实现简单，不容易出错，有bug容易暴露和修复。KISS原则。

RK算法

Rabin-Karp算法，BF算法升级版。
BF算法中，每次检查主串与子串是否匹配，需要依次对比每个字符，BF算法的时间复杂度比较高为O(n*m)。对其稍加改造，引入哈希算法，时间复杂度立刻降低。

算法思想：
通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，说明对应的子串和模式串匹配(暂时忽略哈希冲突)。哈希值是一个数字，数字之间比较是否相等非常快速。
计算子串的哈希值时，依然需要遍历子串中的每个字符，模式串与子串的比较效率提高，算法整体的效率并未提高。

哈希算法设计技巧，假设主串的字符集中只包含K个字符，可用一个K进制数来表示一个子串，这个K进制数转化成十进制数，作为子串的哈希值。
比如要处理的字符串只包含a~z这26个小写字符，可以用二十六进制来表示一个字符串。把a~z这26个字符映射到0~25这26个数字，a表示0，b表示1，以此类推，z表示25。一个包含a到z这26个字符的字符串，计算哈希；
“cba”=’c’*26² + ‘b’*26¹ + ‘a’*26⁰
=2*26² + 1*26¹ + 0*26⁰
=1353

RK算法

/**
* @param main 主串
* @param pattern 模式串
* @return 匹配下标的起始值
*/
public int indexRk(char[] main,char[] pattern) {
    int mLen = main.length;
    int pLen = pattern.length;
    int pHash = hash(pattern,0,pLen);
    for(int i = 0; i < mLen - pLen +1; i++) {
        if(pHash == hash(main, i, pLen))
            return i;
    }
    return -1;
}
/**
* 使用[a-z] 对应[0-25] 26进制计算hash值
* @param chars 字符数组
* @param start 起始下标
* @param len 长度
* @return 匹配下标的起始值
*/
private int hash(char[] chars, int start, int len) {
    int hash = 0;
    int x = 0;
    for(int i = start; i < start + len; i++,x++) {
        hash += Math.pow(26, len - x - 1) * (chars[i] - "a");
    }
    return hash;
}

哈希算法特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系：相邻连个子串s[i-1,i+m-2]和s[i,i+m-1] (i表示子串在主串中的其实位置，子串的长度都为m)，对应哈希值计算公式有交集，可以使用s[i-1]的哈希值快速计算出s[i]的哈希值：
h[i-1]=26^m-1*(s[i-1]-‘a’) + 26^m-2*(s[i]-‘a’) + 26⁰*(s[i+m-2]-‘a’)
h[i]=26^m-1*(s[i]-‘a’)+ + 26¹*(s[i+m-2]-‘a’)+ 26⁰*(s[i+m-1]-‘a’)

B=A26;
h[i]=(h[i-1]-26^m-1\(s[i-1]-‘a’))*26 + 26⁰*(s[i+m-1]-‘a’)

26^m-1可以进一步通过查表提高计算效率，事先计算好26⁰、26¹、26²…26^m-1，并存储在一个长度为m的数组中，公式中的次方就对应数组的下标，需要计算26的x次方的时候，可以直接从数组的下标为x的位置取值，节省重复计算时间。

RK算法优化

/**
     * rk字符串匹配
     * 改良：
     * 1、可以为所有字符串
     * 2、解决存在hash冲突
     * 3、优化hash函数
     *
     * @param
     * @return
     */
    public static int indexRk2(char[] main, char[] pattern) {
        int mLen = main.length;
        int pLen = pattern.length;
        int pHash = hashPrime(pattern, 0, pLen);
        for (int i = 0; i < mLen - pLen + 1; i++) {
            if (pHash == hashPrime(main, i, pLen)) {
                int j = 0, k = i;
                while (main[k++] != pattern[j++] || j > pLen) break;

                return i;
            }
        }
        return -1;
    }

    /**
     * 0-255下所有的质数
     */
    private static char[] PRIME_NUMBERS = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
            101, 103, 107, 109, 113,
            127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
            179, 181, 191, 193, 197, 199, 211};

    /**
     * 使用0-255下所有的质数计算hash值
     *
     * @param chars 字符数组
     * @param start 起始下标
     * @param len   长度
     * @return
     */
    private static int hashPrime(char[] chars, int start, int len) {
        int hash = 0;
        int primeLen = PRIME_NUMBERS.length;
        for (int i = start; i < start + len; i++) {
            hash += PRIME_NUMBERS[Objects.hashCode(chars[i]) % primeLen];
        }
        return hash;
    }

}

时间复杂度：
整个RK算法包含两个部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。
第一部分通过设计特殊的哈希算法，只需要扫描一遍主串就能计算所有子串的哈希值，时间复杂度为O(n)。
第二部分，与每个子串哈希值比较的时间复杂度为O(1)，总共需要比较n-m+1个子串的哈希值，时间复杂度是O(n)
RK算法整体的时间复杂度为O(n)。

其他哈希算法有散列冲突时，再对比一下子串和模式串本身。极端情况下，每次都要再对比子串和模式串本身，时间复杂度退化成O(n*m)。

扩展

一维字符串->二位字符串矩阵