LeetCode_String_28. Implement strStr() 實作 strStr()（C++/Java）【字元串比對，Sunday算法，KMP算法】

一，題目描述

英文描述

中文描述

二，解題思路

1，Sunday算法

1.1 算法實作

1.2 算法原理

2，KMP算法

三，AC代碼

Sunday算法

C++

Java

KMP算法

C++

Java

四，解題過程

第一博

第二搏

第三搏

一，題目描述

原題連結https://leetcode-cn.com/problems/implement-strstr/

英文描述

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Example 1:

Input: haystack = "hello", needle = "ll"

Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"

Output: -1

Example 3:

Input: haystack = "", needle = ""

Output: 0

Constraints:

0 <= haystack.length, needle.length <= 5 * 10^4

haystack and needle consist of only lower-case English characters.

中文描述

實作 strStr() 函數。

給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在，則傳回 -1。

示例 1:

輸入: haystack = "hello", needle = "ll"

輸出: 2

示例 2:

輸入: haystack = "aaaaa", needle = "bba"

輸出: -1

說明:

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

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

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/implement-strstr

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

參考：

@Test【Sunday 解法】具體介紹了Sunday算法的實作；

@LoliconAutomaton【字元串比對——Brute-Force、Sunday以及KMP算法】介紹了不同算法的差別，以及為什麼有效；

@孤~影【（原創）詳解KMP算法】詳細介紹KMP算法原理；

1，Sunday算法

1.1 算法實作

圖源@Test【Sunday 解法】。大佬講解的十厘清晰，就直接拿過來用了

LeetCode_String_28. Implement strStr() 實作 strStr()（C++/Java）【字元串比對，Sunday算法，KMP算法】

1.2 算法原理

當模闆字元串（pattern）與目前子串（curString）比對失敗後，需要考慮向右重新取出子串curString并與pattern進行比較；

普通的暴力解法是【老老實實的向右移一位】，再從目前位置取出新的子串；

Sunday算法就是計算出需要移動的最短距離，怎麼了解最短呢？來舉個栗子吧：

假設原字元串為srcString，目前字元串為curString，curString後一字元為nextChar，模式串為pattern；

LeetCode_String_28. Implement strStr() 實作 strStr()（C++/Java）【字元串比對，Sunday算法，KMP算法】

例一：nextChar不在pattern中

當然可以跳過nextChar了，直接将指針鎖定到nextChar的後一個位置，這裡是4。

最短移動距離為pattern.size() + 1：

LeetCode_String_28. Implement strStr() 實作 strStr()（C++/Java）【字元串比對，Sunday算法，KMP算法】

例二：nextChar為pattern最後一個字元

猜測最好的結果是，向右移動一位正好能完全比對，是以最短移動距離為1；

LeetCode_String_28. Implement strStr() 實作 strStr()（C++/Java）【字元串比對，Sunday算法，KMP算法】

例三：nextChar為pattern倒數第二個字元

猜測最好的結果，紅框中的字元串就是pattern，是以最短移動距離是2；

LeetCode_String_28. Implement strStr() 實作 strStr()（C++/Java）【字元串比對，Sunday算法，KMP算法】

例四：pattern中有重複的字元

在算法實作中寫道：【存儲每一個在模式串中出現的字元，在模式串中出現的最右位置到尾部的距離 +1】。

是以這裡最短距離為1，而不是3，這樣就不會錯過正确答案了。

LeetCode_String_28. Implement strStr() 實作 strStr()（C++/Java）【字元串比對，Sunday算法，KMP算法】

2，KMP算法

參考@孤~影【（原創）詳解KMP算法】，講的非常詳細！下面将關鍵部分摘抄下來，作為記錄。

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;
}

三，AC代碼

Sunday算法

C++

class Solution {
public:
    int strStr(string haystack, string needle) {
        unordered_map<char, int> shift;
        int index = 0;
        // 生成偏移表
        for(int i = 0; i < needle.size(); i++) {
            shift[needle[i]] = needle.size() - i;
        }
        while(index + needle.size() <= haystack.size()) {
            // 比對成功，傳回下标
            if(haystack.substr(index, needle.size()) == needle) return index;
            // 目前子串後一個字元的位置
            int nextCharIndex = index + needle.size();
            // 超出原字元串範圍，傳回-1
            if(nextCharIndex >= haystack.size()) return -1;
            if(shift.find(haystack[nextCharIndex]) == shift.end()) {
                index = index + needle.size() + 1;
            } else {
                index += shift[haystack[nextCharIndex]];
            }
        }
        return -1;
    }
};

Java

字元串中字元的定位要用s.charAt(index)；

字元串截取函數substring()的兩個參數是左右邊界，和C++的substr不同；

class Solution {
    public int strStr(String haystack, String needle) {
        // 這裡使用Integer代替int，否則會報錯
        Map<String, Integer> shift = new HashMap<String, Integer>();
        int index = 0;
        for(int i = 0; i < needle.length(); i++) {
            shift.put(String.valueOf(needle.charAt(i)), needle.length() - i);
        }
        while(index + needle.length() <= haystack.length()) {
            // 比對成功，傳回下标.這裡判斷字元串内容是否相同，要用equals函數
            // StringBuilder curString = new StringBuilder(haystack.substring(index, index + needle.length()));
            // if(needle.equals(curString.toString())) return index;
            if(needle.equals(haystack.substring(index, index + needle.length()))) return index;        
            // 目前子串後一個字元的位置
            int nextCharIndex = index + needle.length();
            // 超出原字元串範圍，傳回-1
            if(nextCharIndex >= haystack.length()) return -1;
            // 目前子串後一個字元的值
            String key = String.valueOf(haystack.charAt(nextCharIndex));
            if(shift.get(key) == null) {
                index = index + needle.length() + 1;
            } else {
                index += shift.get(key);
            }
        }
        return -1;
    }
}

KMP算法

C++

注意size()函數傳回無符号數，與有符号數相比時，需要強制轉化

class Solution {
public:
    vector<int> getNext(string ps) {
        vector<int> next(ps.size(), -1);    // 初始化next數組為-1
        if(ps.size() == 0) return next;     // 當字元串為空時 直接傳回數組 避免在while中通路越界
        int j = 0, k = -1;
        while(j < ps.size() - 1) {
            if(k == -1 || ps[j] == ps[k]) {
                if(ps[++j] != ps[++k]) {
                    next[j] = k;
                } else {
                    next[j] = next[k];
                }
            } else if(ps[j] != ps[k]) {
                k = next[k]; // 第k個字元不比對時将[需要偏移的位置]重新指派給k next[k]小于k，是以看起來是在回溯
            }
        }
        return next;
    }

    int strStr(string haystack, string needle) {
        int i = 0;
        int j = 0;// i為主串指針 j為子串指針
        vector<int> next = getNext(needle);

        // C++中有符号數和無符号數比較時，預設先将有符号數轉換為無符号數再比較
        // 由于j可能為負，是以這裡需要對needle.size()進行強制轉換，確定條件正确
        while(i < haystack.size() && j < int(needle.size())) {
            if(j == -1 || haystack[i] == needle[j]) {
                i++;
                j++;
            } else  {
                j = next[j];
            }
        }
        if(j == needle.size()) {
            return i - j;
        } else {
            return -1;
        }
    }
};

Java

class Solution {
    public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        if(p.length == 0) return next;
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < p.length - 1) {
            if (k == -1 || p[j] == p[k]) {
                if(p[++j] != p[++k]) {
                    next[j] = k;
                } else {
                    next[j] = next[k];
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }
    public int strStr(String haystack, String needle) {
        char[] t = haystack.toCharArray();
        char[] p = needle.toCharArray();
        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        int[] next = getNext(needle);
        while (i < t.length && j < p.length) {
            if (j == -1 || t[i] == p[j]) { // 當j為-1時，要移動的是i，當然j也要歸0
                i++;
                j++;
            } else {
                j = next[j]; // j回到指定位置
            }
        }
        if (j == p.length) {
            return i - j;
        } else {
            return -1;
        }
    }
}

四，解題過程

第一博

俺也一樣ε(┬┬﹏┬┬)3

總之先老規矩，暴力一波

class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int i = 0; i + needle.size() <= haystack.size(); i++) {
            if(haystack.substr(i, needle.size()) == needle) return i;
        }
        return -1;
    }
};

你是否有很多問号？

别問，問就是不知道(⓿_⓿)

第二搏

使用sunday算法。。。

第三搏

使用KMP算法。。。

LeetCode_String_28. Implement strStr() 實作 strStr()（C++/Java）【字元串比對，Sunday算法，KMP算法】

一，題目描述

英文描述

中文描述

二，解題思路

1，Sunday算法

1.1 算法實作

1.2 算法原理

2，KMP算法

三，AC代碼

Sunday算法

C++

Java

KMP算法

C++

Java

四，解題過程

第一博

第二搏

第三搏

繼續閱讀

【python】：布爾運算

sqli-labs第一關--報錯注入練習

python之判斷字元裡面有沒有|8

淺談MFC CSting類拼接效率

C和java中關于字元串與字元數組的定義和轉化

Java：String類字元串與數組之間的轉換

Java中 byte[] 數組與 String 字元串的轉化

對角線周遊LeetCode–對角線周遊

回文樹學習小結

查找算法之二分查找查找算法之二分查找

查找檔案中的字元串

LeetCode-110-平衡二叉樹-C語言

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

LeetCode OJ Binary Tree Right Side View

leetcode809