字符串
KMP
参考力扣28题。此外还有214、459题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int strStr(string haystack, string needle) {
if (needle == "") return 0;
vector<int> next(needle.size(), 0);
for (int i = 2, j = 0; i < needle.size(); ++i) {
while (j > 0 && needle[j] != needle[i-1]) j = next[j];
if (needle[j] == needle[i-1]) next[i] = ++j；
}
for (int i = 0, j = 0; i < haystack.size(); ++i) {
while (j > 0 && haystack[i] != needle[j]) j = next[j];
if (needle[j] == haystack[i]) ++j;
if (j == needle.size()) return i - j + 1;
}
return -1;
}
|