文章目录
-
- 原题题目
- 代码实现（首刷自解）
- 代码实现（二刷自解 DAY 231 C++）
- 代码实现（三刷自解 需要注意细节 DAY 256 C++）
原题题目
代码实现（首刷自解）
class Solution {
public:void getnext(string& str,vector<int>& next){
int i = 0; for(int j=1;j<next.size();++j){
while(str[i] != str[j] && i > 0) i = next[i-1];if(str[i] == str[j]){
next[j] = ++i;}else next[j] = 0;}for(int i=next.size()-1;i>=1;--i)next[i] = next[i-1];}int strStr(string haystack, string needle) {
if(needle == "") return 0;vector<int> next(needle.size(),0);getnext(needle,next);next[0] = -1;int pos1 = 0,pos2 = 0;for(int pos1=0;pos1<haystack.size();){
if(haystack[pos1] == needle[pos2]){
++pos2;++pos1;if(pos2 == needle.size()) return pos1-needle.size();}else{
while(pos2 != -1 && haystack[pos1] != needle[pos2])pos2 = next[pos2];if(pos2 == -1) ++pos2,++pos1;}}return -1;}
};
代码实现（二刷自解 DAY 231 C++）
class Solution {
public:void getnext(vector<int>& next,string& str){
int size = next.size(),pos = 0;for(int i = 1;i < size;++i){
while(str[i] != str[pos] && pos) pos = next[pos-1];pos += (str[i] == str[pos]);next[i] = pos;}for(int i = size-1;i >= 1;--i)next[i] = next[i-1];next[0] = -1;}int strStr(string haystack, string needle) {
if(!needle.size()) return 0;vector<int> next(needle.size(),0);getnext(next,needle);int pos1 = 0,pos2 = 0,size1 = needle.size(),size2 = haystack.size();while(pos1 < size1 && pos2 < size2){
if(pos1 == -1 || needle[pos1] == haystack[pos2]){
++pos1;++pos2;}else pos1 = next[pos1];}if(pos1 != size1) return -1;else return pos2 - size1; }
};
代码实现（三刷自解 需要注意细节 DAY 256 C++）
class Solution {
public:void getnext(vector<int>& next,const string& str){
int pos = 0,size = str.size();for(int i = 1;i < size;++i){
while(pos && str[i] != str[pos]) pos = next[pos - 1];pos = (str[i] == str[pos]) ? pos + 1 : 0;next[i] = pos;}for(int i = size - 2;i >= 0;--i)next[i + 1] = next[i];next[0] = -1;}int strStr(string haystack, string needle) {
if(needle.empty()) return 0;int size = needle.size();vector<int> next(size,0);getnext(next,needle);int i = 0,j = 0,isize = haystack.size(),jsize = needle.size();while(i < isize && j < jsize){
if(haystack[i] != needle[j]){
j = next[j];if(j != -1) continue;}++i;++j;}return j == jsize ? i - jsize : -1;}
};