字符串匹配算法

KMP算法

算法介绍

KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。

KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。

比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。

算法实现

public static int KMPSearch(String target, String pattern) {
    int[] nextVal = getNextVal(pattern);
    int i = 0, j = 0, N = target.length(), M = pattern.length();
    while (i < N && j < M) {
        if (j == -1 || target.charAt(i) == pattern.charAt(j)) { i++; j++; }
        else j = nextVal[j];
    }
    if (j >= M) return i - M;
    return -1;
}
private static int[] getNextVal(String pattern) {
    int[] nextVal = new int[pattern.length()];
    nextVal[0] = -1;
    int i = 0, j = -1;
    int M = pattern.length() - 1;
    while (i < M) {
        if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
            i++; j++;
            if (pattern.charAt(i) == pattern.charAt(j)) nextVal[i] = nextVal[j];
            else nextVal[i] = j;
        } else j = nextVal[j];
    }
    return nextVal;
}

BM算法

算法介绍

Boyer-Moore充分使用预处理P的信息来尽可能跳过更多的字符。通常，我们比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较。这样，就需要将字串中的所有字符一一比较。

Boyer-Moore算法的关键在于，当P的最后一个字符被比较完成后，我们可以决定跳过一个或更多个字符。如果最后一个字符不匹配，那么就没必要继续比较前一个字符。如果最后一个字符未在P中出现，那么我们可以直接跳过T的n个字符，比较接下来的n个字符，n为P的长度（见定义）。

如果最后一个字符出现在P中，那么跳过的字符数需要进行计算（也就是将P整体往后移），然后继续前面的步骤来比较。通过这种字符的移动方式来代替逐个比较是这个算法如此高效的关键所在。

算法实现

public static int BMSearch(String target, String pattern) {
    int[] right = getRight(pattern);
    int N = target.length(), M = pattern.length(), skip = 0;
    for (int i = 0; i <= N - M; i += skip) {
        skip = 0;
        for (int j = M - 1; j >= 0; j--)
            if (pattern.charAt(j) != target.charAt(i + j)) {
                skip = j - right[target.charAt(i + j)];
                break;
            }
        if (skip == 0) return i;
    }
    return -1;
}
private static int[] getRight(String pattern) {
    int[] right = new int[256];
    int M = pattern.length();
    for (int i = 0; i < 256; i++) right[i] = -1;
    for (int i = 0; i < M; i++) right[pattern.charAt(i)] = i;
    return right;
}

RK算法

算法介绍

如果两个字符串hash后的值不相同，则它们肯定不相同；如果它们hash后的值相同，它们不一定相同。

RK算法的基本思想就是：将模式串P的hash值跟主串S中的每一个长度为|P|的子串的hash值比较。如果不同，则它们肯定不相等；如果相同，则再诸位比较之。

~~算法实现 (有问题，按书上敲的，但是结果不对) ~~

public static int RKSearch(String target, String pattern) {
    int N = target.length(), M = pattern.length();
    int R = 256, Q = 997, RM = 1;
    for (int i = 1; i < M; i++)
        RM = (R * RM) % Q;
    long patternHash = hash(pattern, M, R, Q);
    long targetHash  = hash(target,  M, R, Q);
    if (patternHash == targetHash && check(target, pattern, 0)) return 0;
    for (int i = M; i < N; i++) {
        // 减去最前面的hash，加上最后面的hash
        targetHash = (targetHash + Q - RM * targetHash * target.charAt(i - M) % Q) % Q;
        targetHash = (targetHash * R + target.charAt(i)) % Q;
        if (targetHash == patternHash && check(target, pattern, i - M + 1)) return i - M + 1;
    }
    return -1;
}
private static long hash(String key, int M, int R, int Q) {
    long h = 0;
    for (int i = 0; i < M; i++)
        h = (R * h + key.charAt(i)) % Q;
    return h;
}
private static boolean check(String target, String pattern, int i) {
    return pattern.equals(target.substring(i, i + pattern.length()));
}