首页 > 代码库 > leetcode28
leetcode28
题目描述：
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
分析：
这个题目考察的是KMP算法，这个算法的核心是求出子串的自匹配数组，在失配情况下不回溯父串指针（其实是索引），只需将子串向左滑动即可，next数组就是记录了滑动的距离的数组，求next数组是这个算法的难点。
我的第一个版本的代码如下：
#include <iostream>#include <string>#include <vector>using namespace std;int strStr(string haystack, string needle);void getNext(vector<int> &ivec, const string & s);int main(){ cout << "Hello world!" << endl; string hay("mississippi"); string needle("issi"); int res = strStr(hay, needle); cout << "the result of matching:" << res << endl; system("pause"); return 0;}void getNext(vector<int> &ivec, const string & s){ int i = 0, j = -1; ivec[i] = j; while (i < s.size() - 1) { if (j == -1 || s[i] == s[j]) ivec[++i] = ++j; else j = ivec[j]; }}int strStr(string haystack, string needle){ if (needle.size() == 0) return 0; if (haystack.size() == 0) return -1; vector<int> ivec(needle.size(), 0); getNext(ivec, needle); for (auto i = ivec.begin(); i != ivec.end(); i++) cout << *i << endl; int i = 0, j = 0; cout << haystack.size() << " " << needle.size() << endl; while( i < haystack.size() && j < needle.size() ) //while (i != haystack.size() && j != needle.size()) { cout << "before modified " << i << " " << j << endl; if (j == -1 || haystack[i] == needle[j]) { cout << "what" << endl; ++i; ++j; } else { j = ivec[j]; } cout << "after modified " << i << " " << j << endl; } if (j == needle.size()) return i - j; else return -1;}
这份代码我以为可以完美AC了，结果报了wrong answer，我很不理解，经过修改，就是将上一个版本中的while循环头换成下方紧邻的那一行就AC了，经过和大神的讨论，大神很快指出了我的错误所在，那就是C++的隐式类型转换！haystack.size()返回的是一个unsigned int类型，而i， j是int型，在运算时int会隐式转换为unsigned int，而-1转换为unsigned int型之后为4294967295（2的32次方减1）是一个非常大的数字！以前写循环不注意，现在吃了大亏！希望吃一堑长一智吧，以后写代码一定要非常注意类型的选择，注意int和unsigned int不能比较，如果必须比较一定将unsigned int 强制转换为long long类型再比较！最后完成版的代码如下：
#include <iostream>#include <string>#include <vector>using namespace std;int strStr(string haystack, string needle);void getNext(vector<int> &ivec, const string & s);int main(){ string hay("mississippi"); string needle("issi"); int res = strStr(hay, needle); cout << "the result of matching:" << res << endl; system("pause"); return 0;}void getNext(vector<int> &ivec, const string & s){ int i = 0, j = -1; ivec[i] = j; while (i < s.size() - 1) { if (j == -1 || s[i] == s[j]) ivec[++i] = ++j; else j = ivec[j]; }}int strStr(string haystack, string needle){ if (needle.size() == 0) return 0; if (haystack.size() == 0) return -1; vector<int> ivec(needle.size(), 0); getNext(ivec, needle); for (auto i = ivec.begin(); i != ivec.end(); i++) cout << *i << endl; int i = 0, j = 0; long long haystack_size = haystack.size(); long long needle_size = needle.size(); while( i < haystack_size && j < needle_size ) { cout << "i and j before modified " << i << " " << j << endl; if (j == -1 || haystack[i] == needle[j]) { cout << "what" << endl; ++i; ++j; } else { j = ivec[j]; } cout << "i and j after modified " << i << " " << j << endl; haystack_size = haystack.size(); needle_size = needle.size(); } if (j == needle.size()) return i - j; else return -1;}
leetcode28
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。