implement-strstr

题目描述

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1

当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf()) 定义相符。

解决方案

比较简单的想法如下，但是时空消耗是在有点看不过去，最主要的问题是，如果字符串中重复的字符比较多，该算法就显得很蠢。

int strStr(string haystack, string needle) {
	int len1 = haystack.length();
	int len2 = needle.length();
	if (!len2)
		return 0;
	else
	{
		if (!len1)
			return -1;
		int i = -1, j = 0, k = 0;
		while (true)
		{
			j = 0; i++;
			while (i<len1 && haystack[i] != needle[j])
				i++;
			k = i;
			while (k<len1 && j<len2 && haystack[k] == needle[j])
			{
				k++; j++;
			}
			if (j == len2)
				return k - len2;
			if (k >= len1)
				return -1;
		}
	}
}

动态规划是个好东西，可惜我没掌握。

明天大年三十，我还是偷个懒，不学别人的优秀解法了吧。听说KMP 算法（Knuth-Morris-Pratt 算法）是一个著名的字符串匹配算法，效率很高，但是有点复杂。