KMP算法学习

可以先看字符串匹配的KMP算法
针对第16张图的我的理解如下
kmp图

当上面的C与下面的D不能进行匹配的时候
只可能有两种情况

  1. C在匹配的字符串中
  2. C不在匹配的字符串中

由于目标是进行匹配，需要最小的移位达到最大的匹配
即需要C这个字符能和下面的字符串实现最大的匹配
即C的前缀与下面字符串的前缀达到最大的匹配
由于下面部分ABCDAB已经和上面匹配了
可以归到找下面的ABCDAB的最大匹配
即寻找ABCDAB的前缀与后缀的最大匹配
并且需要前缀的后面一位等于当前字符即C
对于该字符串最大前缀便是AB，并且其后一位等于C则匹配到其上

算法实现

问题转化为下面一个字符串的问题，当D不能和上面进行匹配时，需要找到一个前缀最大匹配的后一位去和上面的字符串比较
问题变成了:
当下面的字符串ABCDABD中的某一位与上面字符串不能匹配时，该选择哪一位去与上面的字符串进行匹配保证最大匹配
这时要想怎么去做了
一种做法是拿当前字符的每个前缀去和这个字符串的前缀去比较拿到一个最大的
但时间复杂度较高，显然不好
可以看到，当前字符前缀的最大匹配只依赖于其前面的字符，可以发现这是一个动态规划的问题
可以以next[i]表示当前下标为i不匹配时，需要与上面字符比较的下一个的下标
next[0]=-1 即第0位不匹配时，下面没有字符串与上面字符串匹配
即上面字符串的当前位不属于匹配的字符串中
给出算法实现如下

private static int[] getNext(String pattern) {
    int[] next = new int[pattern.length()];
    next[0] = -1;
    for (int i = 1; i < pattern.length(); i++) {
        int j = i - 1;
        while (next[j] != -1 && !(pattern.charAt(j) == pattern.charAt(next[j]))) {
            j = next[j];
        }
        next[i] = next[j] + 1;
    }
    return next;
}

画个图就比较好理解了
然后就可以用next数组了
完整程序如下

public class KmpAgain {
    public static Boolean kmp(String pattern, String src) {
        int next[] = getNext(pattern);
        int len1 = pattern.length();
        int len2 = src.length();
        int i = 0;
        int j = 0;
        while (i < len2 && j < len1) {
            while (i < len2 && j < len1 && src.charAt(i) == pattern.charAt(j)) {
                j++;
                i++;
            }
            if (j == len1) {
                return true;
            }
            do {
                j = next[j];
            }
            while (j != -1 && src.charAt(i) != pattern.charAt(j));
            if (j == -1) {
                i = i + 1;
                j = 0;
            }
        }
        return false;
    }

    private static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        for (int i = 1; i < pattern.length(); i++) {
            int j = i - 1;
            while (next[j] != -1 && !(pattern.charAt(j) == pattern.charAt(next[j]))) {
                j = next[j];
            }
            next[i] = next[j] + 1;
        }
        return next;
    }
}

private static int[] getNext(String pattern) {
    int[] next = new int[pattern.length()];
    next[0] = -1;
    for (int i = 1; i < pattern.length(); i++) {
        int j = i - 1;
        while (next[j] != -1 && !(pattern.charAt(j) == pattern.charAt(next[j]))) {
            j = next[j];
        }
        next[i] = next[j] + 1;
    }
    return next;
    }
}

第一篇博客，写的比较抽象。

algorithm
algorithm