Implement strStr().Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.class Solution {public: int strStr(string haystack, string needle) { const int len1 = haystack.length(); const int len2 = needle.length(); if(len2 > len1) return -1; if(len2 == 0) return 0; return kmp(haystack, len1, needle, len2); } int kmp(string& haystack, int len1, string& needle, int len2){ vector<int> next = get_next(needle, len2); int i = 0, j = 0; while(i < len1 && j < len2){ if(j == -1 || haystack[i] == needle[j]){ ++i; ++j; } else j = next[j]; } return j == len2 ? i - len2 : -1; } vector<int> get_next(string& needle, int len){ vector<int> next(len, 0); next[0] = -1; int k = -1, j = 0; while(j < len - 1){ if(k == -1 || needle[k] == needle[j]) next[++j] = ++k; else k = next[k]; } return next; }};
