Java-算法-KMP_java kmp算法

一. KMP算法的介绍

0. 前置条件

有两个字符串str1和str2，求str2是否是str1的子串（需连续），若是字串则返回str1中的下标,不存在返回-1.

例1. str1 ="abcd"   str2 = "abcd"  返回0

例2. str1 ="abcd"   str2 = "efgh"  返回-1

例3. str1 ="abcde"   str2 = "bcd"  返回1

1. 常规暴力解法

在遇到第一个不相等的字符后，str2回到首部，而str1回到一开始比较下一个位置

class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i < haystack.length(); i++) {
            int count = i;
            for (int j = 0; j < needle.length(); j++) {
                while (i < haystack.length() && j < needle.length() && haystack.charAt(i) == needle.charAt(j)) {
                    i++;
                    j++;
                }
                if (j == needle.length()) {
                    return i - needle.length();
                }
                else{
                    i = count;
                    break;
                }
            }
        }
        return -1;
    }
}

暴力解法的时间复杂度是非常高的，比如下例：

 在情况给不好的时候时间复杂度会接近O(m*n)

2. KMP的加速过程

  KMP算法是在暴力算法的基础上使用的算法，就是使用了next数组进行加速，先来使用。

 class Solution {
     public int strStr(String haystack, String needle) {
         return getIndexOf(haystack,needle);
    }
    public static int getIndexOf(String s,String m){
        if(s == "" && m == &