【必备算法】字符串（匹配问题）：1.暴力匹配，2.Rabin-Karp，3.KMP

1.暴力匹配

暴力匹配即列出所有子串进行比较

public int forceSearch(String txt, String pat) {
	// 遍历内容串txt，选取起点
    for (int i = 0, j = 0; i < txt.length(); i++) {
    	// 从起点开始与模式串pat对比
        for (j = 0; j < pat.length(); j++) 
            if (pat.charAt(j) != txt.charAt(j)) break;
        if (j == pat.length()) return i;
    }
    return -1;
}

2.Rabin-Karp

暴力优化，枚举所有子串，但不用所有子串都比较（Hash相同再比对）

public static final int D = 256;
public static final int Q = 9997;

public int RabinKarpSearch(String txt, String pat) {
    int M = pat.length(), N = txt.length();
    int patHash = 0, int txtHash = 0;
    // 1.计算txt初始Hash，pat的Hash
    // 注：Hash算法的设计很重要，要尽量避免重复；这里的Hash算法类似二进制转十进制，加权相加
    for (int i = 0; i < M; i++) {
        // 每循环一次就 * D 相当于加权了（取模时防止过大）, pow (256, i) + char(i)
        patHash = (D * patHash + pat.charAt(i)) % Q;
        txtHash = (D * txtHash + txt.charAt(i)) % Q;
    }
    
    // 2.计算最高位权值（左边开始第一位，i）
    // 注：后面要的改变子串相当于将最高位删除，然后加上一个最低位
    int highestPow = 1;
    for (int i = 0; i < M - 1; i++) {
        highestPow = (highestPow * D) % Q;
    }
    
    // 3.列举所有子串，只有Hash值相同的才进行比对；否则更新txtHash进行下一轮
    for (int i = 0, j = 0; i <= N - M; i++) {
        // 3.1 当前子串Hash与patHash相等，可以进行比对（核心！！！）
        if (patHash == txtHash) {
            for (j = 0; j < M; j++) 
               if (txt.charAt(j) != pat.charAt(j)) break;
            if (j == M) return i;
        }
        // 3.2 Hash不相等或匹配失败，更新txtHash
        // 注：1.这里不能用else
        //     2.txtHash = （txtHash - 最高位 + 新的最低位）% Q
        // 				 = （txtHash - (char(i)*highestPow) + char(i+M)) % Q
        //     3.若txtHash < 0，直接加上Q就行（Q取模得到的）
        txtHash = (D * (txtHash - txt.charAt(i) * highestPow) + txt.charAt(i + M)) % Q;
        if (txtHash < 0) txtHash += Q;
	}
    
    return -1;
}

3.KMP

暴力优化，不枚举所有子串

• 子串们的最长相同前后缀表 ----右移补-1-----> next表
• 碰到不匹配的位置，就根据当前位置在next表中的值k，将目标串的k位置移到不匹配位置

参考视频，参考1，参考2

public class KMP {

    /**
     * 求KMP算法的next数组
     * @param pattern 需要进行匹配的模式子串
     * @return KMP算法的next数组
     */
    public static int[] getNext(String pattern) {
        // 因为next数组下标是从1开始的，所以数组长度为字符串长度+1
        int[] next = new int[pattern.length() + 1];
       
        // 数组前两个数字有默认值
        next[0] = 0;
        next[1] = 1;
       
        // 从第二个字符开始计算next数组
        for (int i = 2; i <= pattern.length(); i++) {
           
            // 获取模式串前缀子串
            String subStr = pattern.substring(0, i);
            // 前缀子串的相同前后缀的最大长度
            int max = 0;

            // 求前缀子串的相同前后缀的最大长度
            for (int j = 1; j < i; j++) {
                // 获得长度为j的前缀子串的前缀
                String prefix = subStr.substring(0, j);
                //获 得长度为j的前缀子串的后缀
                String suffix = subStr.substring(subStr.length() - j);
               
                //如果前缀子串的前后缀相等（长度为j）
                if (prefix.equals(suffix)) { 
                    // 更新前缀子串的相同前后缀的最大长度
                    // 这个肯定会越来越大的，j会不断++，最后求出最大长度
                    max = j;
                }
            }
           
            // 将求得的模式串的前缀的最大前后缀长度，写入对应下标的next数组
            next[i] = max;
        }
        // 返回求得的next数组
        return next;
    }

    /**
     * KMP算法的字符串匹配算法
     * @param content 内容串
     * @param pattern 模式串
     * @return 模式串在内容串的索引，跟String类的indexOf()方法的返回值一样，如果未找到返回-1
     */
    public static int match(String content, String pattern) {
        // 如果模式串比内容串还要长
        if (pattern.length() > content.length()) {
            return -1;
        }
       
        // 获取模式串的next数组
        int[] next = getNext(pattern);
       
        // 内容串ci指针和模式串pi指针向前遍历
        for (int ci = 0; ci < content.length(); ci++) {
            for (int pi = 0; pi < pattern.length(); pi++) {
                // 如果内容串已经越界了
                if (ci >= content.length()) {
                    // 超出范围还没找到，返回-1
                    return -1;
                }
               
                // 当前内容串的比较字符
                char charC = content.charAt(ci);
                // 当前模式串的比较字符
                char charP = pattern.charAt(pi);
               
                // 如果两个字符相等
                if (charC == charP) {
                    // 如果匹配到了模式串最后一个字符
                    if (pi == pattern.length() - 1) {
                        // 返回索引
                        return ci - pi;
                    // 如果还没到模式串最后一个字符
                    } else {
                        // 内容串右移一位
                        ci++;
                    }
                // 如果两个字符不相等
                } else {
                    // 找到内容串需要右移的位数
                    int contentRightOffset = pi - next[pi];
                    // 找到内容串的下一个起始坐标
                    int restart = ci - pi + 1 + contentRightOffset
                    // 注意，这里需要-1，应对for循环里面的自增
                    ci = restart - 1;
                   
                    // 跳出当前模式串的for循环，重新匹配模式串
                    break;
                }
            }
        }
        // 找完了还没有找到，返回-1
        return -1;
    }

    /**
     * 测试KMP算法
     * @param args
     */
    public static void main(String[] args) {
        // 测试内容串
        String content = "abaabaabbabaaabaabbabaab";
       
        // 测试模式串
        String pattern = "abaabbabaab";
       
        // 输出模式串在内容串的索引号
        System.out.println(match(content, pattern));
    } 
}