Last active
July 19, 2022 11:26
-
-
Save icameling/6eb18604e1165190c0536491e28c99dc to your computer and use it in GitHub Desktop.
#字符串 #实现strStr
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int strStr(string haystack, string needle) { | |
if (haystack.size() < needle.size()) | |
return -1; | |
if (needle.size() == 0) | |
return 0; | |
for (int i = 0; i < haystack.size() - needle.size() + 1; ++i) { | |
if (haystack[i] == needle[0]) { | |
int k = 0; | |
for (; k < needle.size(); ++k) { | |
if (haystack[i+k] != needle[k]) | |
break; | |
} | |
if (k == needle.size()) | |
return i; | |
} | |
} | |
return -1; | |
} | |
}; | |
// ***************************** KMP ***************************** // | |
class Solution { | |
public: | |
// Partial Match Table 部分匹配表 | |
void get_pmt(const string& patten, int* pmt) { | |
// case1: 先if 后while | |
// a a b a a a c | |
// 0 1 2 3 4 5 6 | |
// j 0 1 0 1 2 (1) 0 | |
// pmt 0 1 0 1 2 (1) 0 | |
// i 1 2 3 4 5 6 7 | |
// case1: 先while 后if | |
// a a b a a a c | |
// 0 1 2 3 4 5 6 | |
// j 0 1 0 1 2 (2) 0 | |
// pmt 0 1 0 1 2 (2) 0 | |
// i 1 2 3 4 5 6 7 | |
pmt[0] = 0; | |
int j = 0; | |
for (int i = 1; i < patten.size(); ++i) { | |
// aabaaac aabaaaac i++ | |
// | => | => | |
// aabaaac aabaaac j++ | |
while (patten[i] != patten[j] && j > 0) { | |
j = pmt[j - 1]; | |
} | |
if (patten[i] == patten[j]) { | |
j++; | |
} | |
pmt[i] = j; | |
} | |
} | |
int kmp(const string& s, const string& patten, int* pmt) { | |
int j = 0; | |
for (int i = 0; i < s.size(); ++i) { | |
while (s[i] != patten[j] && j > 0) { | |
j = pmt[j - 1]; | |
} | |
if (s[i] == patten[j]) { | |
j++; | |
} | |
if (j == patten.size()) | |
return i - j + 1; | |
} | |
return -1; | |
} | |
int strStr(string haystack, string needle) { | |
if (haystack.size() < needle.size()) | |
return -1; | |
if (needle.size() == 0) | |
return 0; | |
int pmt[needle.size()]; | |
get_pmt(needle, pmt); | |
return kmp(haystack, needle, pmt); | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment