首页 > 代码库 > 70. Implement strStr() 与 KMP算法
70. Implement strStr() 与 KMP算法
Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
MY: Question.
思路： 逐步查找。当出现不同时，如何回溯是关键。
Solution A:
class Solution {public: char *strStr(char *haystack, char *needle) { int i = 0, j = 0; while(haystack[i] != ‘\0‘ && needle[j] != ‘\0‘) { if(haystack[i] == needle[j]) ++i, ++j; else i = i-j+1, j = 0; } return needle[j] == ‘\0‘ ? haystack+(i-j) : NULL; }};Solution B 与经典 KMP 算法：
对模式串 P 设置回溯数组 next. （next 只有模式串 P 的特性有关系，与目标串没有关系。）
next 的求法:
next[0] = 0; (0 位置最后匹配，下次还从此位置开始匹配（舍去从-1开始，没有意义）)
next[pos] = (P[next[pos-1]] == P[pos] ? next[pos-1]+1 : 0);
(若回溯后的字符与当前字符相同，则应设置回溯位置在前回溯位置之后。否则，设置回溯位置为0)
模式串中：
当前位置 pos 不能匹配时， 回溯到 next[pos-1] 重新开始匹配。
当前位置匹配，则继续下去。
#include <iostream> #include <vector>using namespace std; void getNext(char *P, vector<int> &next) { for (int i = 0; P[i] != ‘\0‘; ++i) { if (i == 0) next.push_back(0); else next.push_back((P[i] == P[next[i-1]]) ? next[i-1]+1 : 0); }}class Solution {public: char *strStr(char *haystack, char *needle) { vector<int> next; getNext(needle, next); int i = 0, j = 0; while (haystack[i] != ‘\0‘ && needle[j] != ‘\0‘) { if (haystack[i] == needle[j]) ++i, ++j; else if (j == 0) ++i; else j = next[j-1]; } return needle[j] == ‘\0‘ ? haystack+(i-j) : NULL; }};int main() { char *T = "missiissippi", *P = "issip"; cout << (Solution().strStr(T, P) ? Solution().strStr(T, P) : "NULL") << endl; return 0; }
70. Implement strStr() 与 KMP算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。