Leetcode: 28. Implement strStr()

Description

Implement strStr().

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

思路

• 字元串匹配問題
• KMP，計算匹配串str的next值時，next[i]的值就是字元串的前i個字元組成的字元串的首碼和尾碼相同字元的最大長度

代碼

class Solution {
public:
    int strStr(string haystack, string needle) {
        int len1 = haystack.size(), len2 = needle.size();
        
        if(len2 == 0) return 0;
        if(len1 == 0) return -1;
        
        vector<int> nums(len2 + 1, 0);
        getNext(needle, nums, len2);
        
        int i = 0, k = 0;
        while(i < len1){
           
            if(k == -1 || haystack[i] == needle[k]){
                ++i;
                ++k;
            }
            else{
                k = nums[k];
            }
            if(k == len2) return i - len2;
        }
        
        return -1;
    }
    
    void getNext(string &str, vector<int>& nums, int len){
        nums[0] = -1;
        
        int j = 0, k = -1;
        while(j < len){
            if(k == -1 || str[j] == str[k]){
                ++j;
                ++k;
                nums[j] = k;
            }
            else k = nums[k];
        }
    }
};