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