LeetCode 28. Implement strStr()（字符串匹配问题） LeetCode

题目描述：

Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
例子：

Input: haystack = "hello", needle = "ll" Output: 2

Input: haystack = "aaaaa", needle = "bba" Output: -1

分析：
题意：给定两个字符串haystack和needle，查找needle在haystack中首次出现的首位置，并返回。
思路：经典的字符串匹配问题，解决方法有暴力匹配算法和KMP算法。我们这里分别展开说明一下。
① 暴力匹配算法：假设现在文本串haystack匹配到i位置，模式串needle匹配到j位置，如果当前字符匹配成功（即haystack[i] == needle[j]），则i++，j++，继续匹配下一个字符；如果匹配失败（即haystack[i] != needle[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i回溯，j被置为0。
假设两个字符串的长度分别为n1、n2，则时间复杂度为O(n1 * n2)。
代码：

#include using namespace std; // violent Match // T(n) = O(n1 * n2) class Solution { public: int strStr(string haystack, string needle) { int n1 = haystack.length(), n2 = needle.length(); // Exceptional Case: if(n1 == 0 && n2 == 0){ return 0; } else if(n1 == 0 && n2 != 0){ return -1; } else if(n1 != 0 && n2 == 0){ return 0; } if(n1 < n2){ return -1; } int i = 0, j = 0; while(i < n1 && j < n2){ if(haystack[i] == needle[j]){ i++; j++; } else{ i = i - j + 1; j = 0; } } if(j == n2){ return i - j; } return -1; } };

② KMP算法：这个算法由Donald Knuth、Vaughan Pratt和James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法为Knuth-Morris-Pratt字符串查找算法，简称为 “KMP算法”。算法流程如下所示：
假设现在文本串haystack匹配到i位置，模式串needle匹配到j位置。Ⅰ. 如果j = -1，或者当前字符匹配成功（即haystack[i] == needle[j]），都令i++，j++，继续匹配下一个字符；Ⅱ. 如果j != -1，且当前字符匹配失败（即haystack[i] != needle[j]），则令i不变，j = next[j]。相当于匹配失败时，模式串needle相对于文本串haystack向右移动了j - next[j]位。
匹配失败时，KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。next数组是KMP算法的精髓所在，也是KMP算法和暴力匹配算法的本质区别！
匹配失败时，模式串needle向右移动的位数为：失配字符所在位置 - 失配字符对应的next值（next数组求解在下文介绍），即移动的实际位数为：j - next[j]，此值大于等于1。
next 数组各值含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。如果next[j] = k，代表j之前的字符串中有最大长度为k的相同前缀后缀。此也意味着在某个字符失配时，该字符对应的next值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next[j]的位置）。Ⅰ. 如果next[j]等于0或-1，则跳到模式串的开头字符；Ⅱ. 若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。
next数组求解过程：我们以模式串needle="ABCDABD"为例。

字符子串	前缀	后缀	共有元素	长度
"A"	?	?	?	0
"AB"	{"A"}	{"B"}	?	0
"ABC"	{"A", "AB"}	{"BC", "C"}	?	0
"ABCD"	{"A", "AB", "ABC"}	{"BCD", "CD", "D"}	?	0
"ABCDA"	{"A", "AB", "ABC", "ABCD"}	{"BCDA", "CDA", "DA", "A"}	"A"	1
"ABCDAB"	{"A", "AB", "ABC", "ABCD", "ABCDA"}	{"BCDAB", "CDAB", "DAB", "AB", "B"}	"AB"	2
"ABCDABD"	{"A", "AB", "ABC", "ABCD", "ABCDA", "ABCDAB"}	{"BCDABD", "CDABD", "DABD", "ABD", "BD", "D"}	?	0

模式串needle="ABCDABD"对应的next数组值为[0,0,0,0,1,2,0]。
假设两个字符串的长度分别为n1、n2，则时间复杂度为O(n1 + n2)。

【LeetCode 28. Implement strStr()（字符串匹配问题）】代码：

#include using namespace std; // KMP Match // T(n) = O(n1 + n2) class Solution { private: int *next; void getNextVal(string needle, int n2){ // create next = new int[n2]; next[0] = -1; int j = 0, k = -1; while(j < n2 - 1){ if(k == -1 || needle[j] == needle[k]){ j++; k++; next[j] = k; } else{ k = next[k]; } } }public: int strStr(string haystack, string needle) { int n1 = haystack.length(), n2 = needle.length(); // Exceptional Case: if(n1 == 0 && n2 == 0){ return 0; } else if(n1 == 0 && n2 != 0){ return -1; } else if(n1 != 0 && n2 == 0){ return 0; } if(n1 < n2){ return -1; } // get next array getNextVal(needle, n2); // KMP int i = 0, j = 0; while(i < n1 && j < n2){ if(j == -1 || haystack[i] == needle[j]){ i++; j++; } else{ j = next[j]; } } if(j == n2){ return i - j; } return -1; } };