面试经典 150 题 22 —（数组 / 字符串）— 28. 找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标

方法一

class Solution {
public:int strStr(string haystack, string needle) {if(haystack.find(needle) == string::npos){return -1;}return haystack.find(needle);}
};

方法二

class Solution {
public:int strStr(string haystack, string needle) {int haystackLength = haystack.length();int needleLength = needle.length();int haystackIndex = 0, needleIndex = 0;while(haystackIndex < haystackLength){if(haystack[haystackIndex] != needle[needleIndex]){// 如果不相等，haystack从最开始匹配相等的地方重新进行haystackIndex = haystackIndex - needleIndex; // needle从头开始needleIndex = 0;}else{if(needleIndex == needleLength-1){return haystackIndex-needleLength+1;}needleIndex++;}haystackIndex++;}return -1;}
};

class Solution {
public:int strStr(string haystack, string needle) {int haystackLength = haystack.size(),needleLength = needle.size();if(needleLength == 0){return 0;}// KMP算法：如果已经匹配的字符串包含相同的前缀和后缀，遇到下一个不匹配的位置时，指向needle的指针跳转到前缀的后一个位置，还是不匹配的话，再往前跳转后继续比较；先构造一个next数组来记录needle指针跳转的位置// 先构造next数组，next数组中的元素表示当前两个元素不匹配时，needle指针要跳转的位置// haystack: [a, b, e, a, b, a, b, e, a, b, f]// needle:   [a, b, e, a, b, f]// next:     [0, 0, 0, 1, 2, 0]vector<int> next(needleLength);for(int i=1,j=0; i<needleLength; i++){while(j>0 && needle[i]!=needle[j]) {j = next[j-1]; // 一直和前一位置的值比较，直到遇到相等的字符或者j=0；j通过next[j-1]来回退}if(needle[i]==needle[j]){j++;};next[i] = j;}// 利用next数组进行跳转匹配，不再需要回退haystack的指针ifor(int i=0,j=0; i<haystackLength; i++){// 匹配不成功，needle指针j回退并继续比较while(j>0 && haystack[i]!=needle[j]){j = next[j-1];}if(haystack[i]==needle[j]){j++;}if(j==needleLength){return i - needleLength + 1;}}return -1;}
};