数组与字符串10-实现 strStr()

使用KMP算法实现 strStr()

一 题目
源自leetcode官网

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
二 暴力破解法

对于此题，可以使用暴力破解法。如上图所示，将needle的第一个字符依次与haystack中的字符比较，若不相等，则换成haystack中的第二个字符，若相等，则将needle的第二个字符与haystack比较字符的下一个字符相比较。若needle中所有字符都已经比较完成且等于haystack相对位置的字符，则找到答案。
代码：

class Solution {
    
    public int strStr(String haystack, String needle) {
    
        int index = -1;
        if(needle.isBlank()){
    
            index = 0;
        } else {
    
            char[] hay = haystack.toCharArray();
            char[] need = needle.toCharArray();
            for(int i = 0;i<hay.length;i++){
    
                int j=0, tmp = i;
                while (j<needle.length()&&tmp<hay.length&&hay[tmp]==need[j]){
    
                    tmp++;
                    j++;
                }
                if(j>=needle.length()){
    
                    index=i;
                    break;
                }
            }
        }
        return index;
    }
}

运行结果：
运行效率太低。

三 使用KMP算法来求解
KMP算法是一种改进的字符串匹配算法。其核心思想是：根据公共前后缀为needle字符串创建一个回退数组next.
如下图所示：到红框位置，字符串needle与haystack不匹配。按暴力破解法，应从haystack字符串的第二个字符开始，重新与needle的第一个字符相比较。但我们观察这两个字符串可知，橙色框的字符与蓝色框的字符相匹配，且对于needle字符串，C之前的字符，蓝色框与绿色框的字符串相等。因此可以等价于橙色框已经和绿色框做了比较，此时，我们可以将橙色框的下一个字符与绿色框的下一个字符比较。若相等，则字符继续往下移动，不相等，就再找匹配字符串。为了知道每次不匹配时，我们应该回退到needle字符串哪里，便为needle字符串创建一个next数组。
next数组为int[] next，数组的索引为needle字符串索引，值为应该回退的位置。将needle转化为字符数组，对于needle[i]，能回退的位置为needle[0]到needle[i-1]之后最大的公共前后缀+1的位置。对于下图所示的needle,对于c字符串所在的位置，其needle[0]到needle[i-1]为ababa,前缀有: a, ab,aba,abab,后缀有：baba,aba,ba,a，因此最大公共前后缀为aba。此时next[5]=3。
对于next数组，有两个特征，若needle[j+1]最大值为next[j]+1.若next[j+1]不等于needle[next[j]+1]，则next[j+1]可能的最大值为next[next[j]]+1。依次类推。可以得到next数组。

class Solution {
    
    public int strStr(String haystack, String needle) {
    
        int index = -1;
        if(needle.isBlank()){
    
            index = 0;
        } else {
    
            int[] next = new int[needle.length()];
            createNext(next,needle);
            int i = 0;
            int j =0;
            while (j<needle.length() && i<haystack.length()){
    
                if(haystack.charAt(i)==needle.charAt(j)){
    
                    i++;
                    j++;
                }else{
    
                    j=next[j];
                    if(j==-1){
    
                        i++;
                        j++;
                    }
                }
            }
            if(j>=needle.length()){
    
                index = i-j;
            }
        }
        return index;
    }
    private void createNext(int[] next,String needle){
    
        char[] tmp = needle.toCharArray();
        next[0] = -1;
        int i = 0,j=-1;
        while(i<needle.length()-1){
    
            if(j==-1 || tmp[i]==tmp[j]){
    
                next[++i]=++j;
            }else{
    
                j=next[j];
            }
        }
    }
}

运行结果：