【Leetcode】【Easy】Implement strStr()

Implement strStr().

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

?

解題：

本題為典型的KMP算法考察題，KMP算法描述為：

　　設主串S，匹配串P，i為S的索引下標，j為P的索引下標，初始i和j設置為0。

　　在i小于S的長度和j小于P的長度時，開始循環：

　　1、比較S[i]和P[j]是否相同；

　　2、如果相同則i++，j++，返回執行第1步；

　　3、如果不同，則計算已匹配成功的P[0]~P[j-1]中，相同前綴和后綴的最大長度，設為n；

　　4、令i不變，j為n（指向相同前后綴的后一個字符），返回執行第1步；

　　循環結束時，查看j值是否等于P的長度，如果等于則匹配成功，否則主串中不包含匹配串。

計算最長相同前后綴：

　　新建一個數組a，數組長度為匹配串P長度。數組的每一位a[i]，表示由P[0]~P[i]表示的字符串，最長相同前后綴的位數；

　　a[0]初始化為0，令i為1，j為0，對于a[i]（0<i<len）有兩種情況：

　　1、如果P[j] == P[i]，那么a[i] = a[i - 1] + 1；

　　　 ?接著j++，i++重新執行第一步；

　　2、當P[j] !=?P[i]，如果j此時為0，表示由P[0]~P[i]組成的字符串沒有相同的前綴和后綴，所以a[i]=0，i++繼續進行第一步；

　　3、當P[j] !=?P[i]，并且j不為0，表示可能包含相同前綴和后綴，則令j = a[j - 1]，繼續執行第一步；

　　直到計算出所有a[i]的值。

?

AC代碼見：

class Solution {
public:
    int strStr(char *haystack, char *needle) {
        int num = strlen(needle);
        int *next = new int[num];
        getNext(needle, next);
        
        int i = 0;
        int j = 0;        
        while (haystack[i] != '\0' && needle[j] != '\0') {
            if (haystack[i] == needle[j]) {
                ++i;
                ++j;
            } else if (j == 0) {
                ++i;
            } else {
                j = next[j - 1];
            }
        }
        
        free(next);
        if (needle[j] != '\0')
            return -1;
        else
            return i - j;
    }
    
    void getNext(char *needle, int *next) {
        int i = 1;
        int j = 0;
        next[0] = 0;
        while (needle[i] != '\0') {
            if (needle[i] == needle[j]) {
                next[i] = j + 1;
                ++i;
                ++j;
            } else if (j == 0) {
                next[i] = 0;
                ++i;
            } else {
                j = next[j - 1];
            }
        }
    }
};

?

代碼優化：

實際編寫中，為了避免判定j是否為0，簡化操作。可以設定next數組，取代a數組。next的含義是，當kmp算法需要尋找子串下一個比較的位置時，直接從next數組中取值；

其中next[0] = -1作為哨兵位，next[i] = a[i - 1]，即將a數組整體后移一位保存在next數組中。

AC代碼如下：

class Solution {
public:
    int strStr(char *haystack, char *needle) {
        int num = strlen(needle);
        int *next = new int[num];
        getNext(needle, next);
        
        int i = 0;
        int j = 0;        
        while (haystack[i] != '\0' && j < num) {
            if (j == -1 || haystack[i] == needle[j]) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        
        free(next);
        if (needle[j] != '\0')
            return -1;
        else
            return i - j;
    }
    
    void getNext(char *needle, int *next) {
        int i = 0;
        int j = -1;
        int strl = strlen(needle);
        next[0] = -1;
        while (i < strl - 1) {
            if (j == -1 || needle[i] == needle[j]) {
                next[++i] = ++j;
            } else {
                j = next[j];
            }
        }
    }
};

?