leetcode 刷题之路 48 Implement strStr()

本文主要是介绍leetcode 刷题之路 48 Implement strStr()，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Implement strStr().

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

字符串匹配。

这里给出KMP算法的实现，还可以用BF，BM算法等。

class Solution {
public:char *strStr(char *haystack, char *needle){if (haystack == NULL || needle == NULL)return NULL;int len1 = strlen(needle);int len2 = strlen(haystack);if (len1 == 0)return haystack;int *next = new int[len1];getNext(next, needle);int i = 0, j = 0;while (i<len2&&j<len1){if (j == -1 || haystack[i] == needle[j]){j++;i++;}else{j = next[j];}if (j == len1)return &(haystack[i - len1]);}return NULL;}void getNext(int *next, const char* needle){int i = 0, k = -1;next[0] = -1;int len = strlen(needle);while (i<len-1){if (k == -1 || needle[i] == needle[k]){if (needle[++k] == needle[++i])next[i] = next[k];elsenext[i] = k;}elsek = next[k];}}
};

这篇关于leetcode 刷题之路 48 Implement strStr()的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---