leetcode 28 Find the Index of the First Occurrence in a String

 直接用kmp算法

class Solution {
public:
    int strStr(string haystack, string needle) {
        return kmp(haystack,needle);
    }

    int kmp(std::string &text,std::string &pattern){
        int n = text.size();
        int m = pattern.size();
        if(m == 0)
            return 0;
        std::vector<int> next;
        next.reserve(m);
        getNext(pattern,m,next);
        int j = -1;
        for(int i = 0;i < n;i++){
            while(j != -1 && text[i] != pattern[j+1]){
                j = next[j];
            }
            if(text[i] == pattern[j+1]){
                j++;
            }
            if(j == m-1)
                return i - j;
        }
        return -1;
    }

    void getNext(std::string &pattern,int len,std::vector<int> &next){
        next[0] = -1;
        int j = -1;
        for(int i = 1;i < len;i++){
            while(j != -1 && pattern[i] != pattern[j+1]){
                j = next[j];
            }
            if(pattern[i] == pattern[j+1])
                j++;
            next[i] = j;
        }
    }
};

或者另外一种写法，用的是部分匹配值(Partial Match)表

class Solution {
public:
    int strStr(string haystack, string needle) {
        return KMP(haystack,needle);
    }
    void getPM(std::string &pattern,int len,std::vector<int> &pm){
        pm[0] = 0;
        int j = 0;// j表示前缀的末尾元素的索引位置,同时它也是最长公共前后缀的长度
        //i表示后缀的末尾元素的索引位置
        for(int i = 1;i < len;i++){
            while(j > 0 && pattern[i] != pattern[j])
                j = pm[j-1];
            if(pattern[j] == pattern[i]) j++;
            pm[i] = j;
        }
    }
    int KMP(std::string &text,std::string& pattern){
        int m = pattern.size();
        if(m == 0) return 0;
        std::vector<int> pm;
        pm.resize(m);
        getPM(pattern,m,pm);
        int n = text.size();
        int j = 0;
        for(int i = 0;i < n;i++){
            while(j > 0 && text[i] != pattern[j])
                j = pm[j-1];
            if(text[i] == pattern[j]) j++;
            if(j == m)
                return i-j+1;
        }
        return -1;
    }
};