C++版 - Leetcode 28.Implement strStr() 解题报告【C库函数strstr()模拟-字符串中子串首次出现的地址】

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
using namespace std; 
// LeetCode, Implement strStr()
// KMP 时间复杂度O(N+M)，空间复杂度O(M)
class Solution {
	public:
		int strStr(const string& haystack, const string& needle) {
			return kmp(haystack.c_str(), needle.c_str());
		}
	private:
		/*
		* @brief  计算部分匹配表，即next数组 
		**
		@param[in] pattern：模式串 
		* @param[out] next：next数组 
		* @return：无 
		*/
		static void compute_prefix(const char *pattern, int next[]) {
			int i;
			int j = -1;
			const int m = strlen(pattern);
			next[0] = j;
			for (i = 1; i < m; i++) {
				while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];
				if (pattern[i] == pattern[j + 1]) j++;
				next[i] = j;
			}
		}
		/*
		* @brief KMP
		**
		@param[in] text
		* @param[in] pattern
		* @return 失败则返回-1，成功匹配时返回第一次匹配的位置
		*/
		static int kmp(const char *text, const char *pattern) {
			int i;
			int j = -1;
			const int n = strlen(text);
			const int m = strlen(pattern);
			if (n == 0 && m == 0) return 0; /* "", "" */
			if (m == 0) return 0; /* "a", "" */
			int *next = (int*)malloc(sizeof(int) * m);
			compute_prefix(pattern, next);
			for (i = 0; i < n; i++) {
				while (j > -1 && pattern[j + 1] != text[i]) j = next[j];
				if (text[i] == pattern[j + 1]) j++;
				if (j == m - 1) {
					free(next);
					return i-j;
				}
			}
			free(next);
			return -1;
		}
};
// 下面是测试
int main()
{
    Solution sol;
    string str1="To be or not to be";
    string str2="be";          
	cout<<sol.strStr(str1, str2)<<endl;
    return 0;
}