leetcode笔记:Implement strStr()

发布时间:2017-09-05 10:37:21
leetcode笔记:Implement strStr()

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

二.题目分析

实现strstr()函数。返回needle(关键字)在haystack(字符串)中第一次出现的位置,如果needle不在haystack中,则返回-1。由于使用暴力方法的时间复杂度为O(mn)会超时,可使用著名的KMP算法解决。该是由Knuth,Morris,Pratt共同提出的字符串匹配算法,其对于任何字符串和目标字符串,都可以在线性时间内完成匹配查找,是一个非常优秀的字符串匹配算法。

三.示例代码

KMP算法:

class Solution { public: void getNext(vector &next, string &needle) { int i = 0, j = -1; next[i] = j; while (i != needle.length()) { while (j != -1 && needle[i] != needle[j]) j = next[j]; next[++i] = ++j; } } int strStr(string haystack, string needle) { if (haystack.empty()) return needle.empty() ? 0 : -1; if (needle.empty()) return 0; vector next(needle.length() + 1); getNext(next, needle); int i = 0, j = 0; while (i != haystack.length()) { while (j != -1 && haystack[i] != needle[j]) j = next[j]; ++i; ++j; if (j == needle.length()) return i - j; } return -1; } };

四.小结

对于这题,还有其他一些有名的算法,如Rabin-Karp和Boyer-Moore算法。

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:孝感网站建设 http://xiaogan.45qun.com