kmp问题

KMP算法
【题目】
给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有字串match，则返回match在str中的开始位置，不含有则返回-1。
【举例】
str=“acbc”，match=“bc”。返回2。
str=“acbc”，match=“bcc”。返回-1。
【要求】
如果match的长度大于str长度(M>N)，str必然不会含有match，可直接返回-1。但如果N>=M，要求算法复杂度O(N)。

原来复杂度是O(MN) 现在复杂度是O(N)

next数组生成只和match有关系

还是利用了前面的信息

next[i] 前面那一坨字符串的指标 O(M)

前缀和后缀相等的最长前缀

123123b next[b]=3 前缀不能包含最后一个字符后缀不能包含第一个字符

最长前缀和最长后缀相同

next[0]=-1 next[1]=0 next[2]=

平移到next的位置加大了匹配的步长

本来应该匹配 i+1 但是现在直接匹配

反证法证明假设中间可以匹配

则next[i]的值就算错了呀矛盾所以可以大跨步

match一直在移动最多推动到n 所以复杂度是O(N) 为什么呢?

public int getIndexOf(String s, String m) {
     if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
        return -1;
        }
     char[] ss = s.toCharArray();
     char[] ms = m.toCharArray();
     int si = 0;
     int mi = 0;
     int[] next = getNextArray(ms);
     while (si < ss.length && mi < ms.length) {
        if (ss[si] == ms[mi]) {
            si++;
            mi++;
        } else if (next[mi] ==   -1) {    //这里只可能有一种情况就是第一个字符串没有匹配上？
            si++;
        } else {
            mi = next[mi];      //如果为0呢？
        }
     }
     return mi == ms.length ? si - mi : -1;
    }

  public int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < next.length) {
            if (ms[pos - 1] == ms[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }