题目：28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

题意：

该题目就是实现strstr()函数，该函数C语言原型如下：返回字符串str1在str2中的位置。

1

extern char *strstr(char *str1, const char *str2);

解法：

暴力求解法

最直接的实现方式就是暴力求解法，如下代码所示，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
	public:
		int strStr(string haystack, string needle) {
			return bruth(haystack, needle);
		}

	private:
		int bruth(string text, string pattern) {
			int M = pattern.length();
			int N = text.length();
			if (M == 0) return 0;
			if (N == 0) return -1;
			for (int i = 0; i <= N - M; ++i) {
				int j = 0;
				for (; j < M; ++j) {
					if (text.at(i + j) != pattern.at(j))
						break;
				}
				if (j == M) return i;
			}
			return -1;
		}
}

在最坏的情况下，暴力子字符串查找算法在长度为N的文本中查找长度为M的模式字符串需要O(NM)次字符串比较。

我们可以将上面的实现方法进行一定的修改，让大家能看到i指针的回退，如下代码所示，当i指针指向字符和j指向字符发生失配，i便会回退j个位置（此时j是失配前模式串的匹配项个数），同时j指向模式串的第一个位置。该段代码和上面代码其实是等效的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
	int strStr(string haystack, string needle) {
		return bruth(haystack, needle);
	}

private:
	int bruth(string text, string pattern) {
		int M = pattern.length();
		int N = text.length();
		if (M == 0) return 0;
		if (N == 0) return -1;
		int i = 0;
		int j = 0;
		for (; i < N && j < M; ++i) {
			if (text.at(i) == pattern.at(j)) j++;
			else {	i -= j; j = 0; }
		}
		if (j == M) return i - M;
		else return -1;
	}
}

那我们就可以很明显的看到，当模式串中j指向位置字符不匹配的时候，其实前面通过匹配我们已经获知了一部分文本的情况，因此如果能够利用这一部分已知的情况来加大模式串移动的有效性。KMP算法就是利用字符串匹配失效之前部分匹配的这个有用信息，通过保持文本指针不回退，仅有效移动模式字符串的位置来进行有效查找的。

KMP算法

KMP算法常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人同时独立发现，后取这3人的姓氏命名此算法. 大家可以参看july的Blog，讲解的是我目前看到最详细的了。

KMP算法实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

 class Solution {
	public:
		int strStr(string haystack, string needle) {
			return kmp(haystack, needle);
		}
	private:
		// KMP
		int kmp(string text, string pattern) {
			int M = pattern.length();
			int N = text.length();
			if (M == 0) return 0;
			if (N == 0) return -1;
			int i = 0;
			int j = 0;
	
			int* next = new int[M];
			calculateNext(pattern, next);
			for (; i < N && j < M; ++i) {
				if ( j == -1 || text.at(i) == pattern.at(j) ) j++;
				else { i--; j = next[j]; }	// i维持不变，j跳转位置由next数组决定
			}
			delete[] next;
	
			if (j == M) return i - M;
			else return -1;
		}
		void calculateNext(string pattern, int* next) {
			if (pattern.length() == 0 || next == nullptr) return;
			next[0] = -1;
			int i = 0;
			int k = -1;
			while (i < pattern.length() - 1) {
				if (k == -1 || pattern.at(k) == pattern.at(i)) {
					++i;
					++k;
					next[i] = k;
				}
				else {
					k = next[k];
				}
			}
		}
	}