子字符串查找

1 暴力破解

 

java实现如下：

public class Naive {

    /**
     * 暴力破解
     *
     * @param pat
     * @param txt
     * @return
     */
    private static int search(String pat, String txt) {
        int m = pat.length();
        int n = txt.length();
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (txt.charAt(i + j) != pat.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return n;
    }

    public static void main(String[] args) {
        int pos = search("abcabd", "abcabcabdabba");
        System.out.println(pos);
    }

}

 最坏的情况是：

常见的是二进制情况下的匹配：

 

 

 

2 KMP算法

如果用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间：

 

所以，kmp方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间。

public class KMP {
    public static int KMP(String pat, String txt) {
        char[] t = pat.toCharArray();
        char[] p = txt.toCharArray();

        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        int[] next = getNext(txt);

        while (i < t.length && j < p.length) {
            if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
                i++;
                j++;
            } else {
                // i不需要回溯了
                // i = i - j + 1;
                j = next[j]; // j回到指定位置
            }
        }

        if (j == p.length) {
            return i - j;
        } else {
            return -1;
        }
    }

    public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;

        int j = 0;
        int k = -1;
        while (j < p.length - 1) {
            if (k == -1 || p[j] == p[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String pat = "abcabd";
        String txt = "abcabcabdabba";
        int pos = KMP(pat, txt);
        System.out.println(pos);
    }

}

 

kmp算法的核心时间复杂度就是O（m+n）