Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Update (2014-11-02):The signature of the function had been updated to return theindexinstead of the pointer. If you still see your function signature returns achar *orString, please click the reload buttonto reset your code definition.
题意：找到第一次匹配的下标。
思路：KMP模板题。
class Solution {public:void getNext(char *patten, vector<int> &next) {int i = 0, j = -1;int len = strlen(patten);next.resize(len+1);next[0] = -1;while (i < len) {if (j == -1 || patten[i] == patten[j]) {i++, j++;next[i] = j;} else j = next[j];}}int strStr(char *haystack, char *needle) {if (haystack == NULL || needle == NULL)return -1;int i = 0, j = 0;int lena = strlen(haystack);int lenb = strlen(needle);vector<int> next;getNext(needle, next);while (i < lena && j < lenb) {if (j == -1 || haystack[i] == needle[j])i++, j++;else j = next[j];}if (j == lenb)return i – j;else return -1;}};
，往往教导我们大家要好好学习天天向上，
