KMP算法 LeetCode 28. 實作 strStr()

題目

實作 strStr() 函數。

給你兩個字元串 haystack 和 needle ，請你在 haystack 字元串中找出 needle 字元串出現的第一個位置（下标從 0 開始）。如果不存在，則傳回  -1 。

 

說明：

當 needle 是空字元串時，我們應當傳回什麼值呢？這是一個在面試中很好的問題。

對于本題而言，當 needle 是空字元串時我們應當傳回 0 。這與 C 語言的 strstr() 以及 Java 的 indexOf() 定義相符。

 

示例 1：

輸入：haystack = "hello", needle = "ll"
輸出：2
示例 2：

輸入：haystack = "aaaaa", needle = "bba"
輸出：-1
示例 3：

輸入：haystack = "", needle = ""
輸出：0
 

提示：

0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 僅由小寫英文字元組成
           

解題思路

KMP算法

詳細教程

代碼

class Solution {
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i<s.length(); i++){
            while(j>=0 && s.charAt(i) != s.charAt(j+1)){
                j=next[j];
            }

            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }

        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for(int i = 0; i<haystack.length();i++){
            while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            if(haystack.charAt(i)==needle.charAt(j+1)){
                j++;
            }
            if(j==needle.length()-1){
                return (i-needle.length()+1);
            }
        }

        return -1;
    }
}