查找子字符串问题，相关可以参考《算法4》5.3节。
😜kmp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int strStr(string haystack, string needle) {
if(needle == "")
return 0;
vector<vector<int > > df = dfa(needle);
int j = 0;
int i = 0;
for(; i < haystack.size() && j != needle.size(); ++i) {
j = df[haystack.at(i)][j];
}
if(j == needle.size()) return i - needle.size();
return -1;
}
vector<vector<int> > dfa(string s) {
vector<vector<int> > v(128, vector<int>(s.size()));
v[s.at(0)][0] = 1;
for(int i = 1, X = 0; i < s.size(); ++i) {
for(int j = 0; j < 128; ++j) {
v[j][i] = v[j][X];
}
v[s.at(i)][i] = i + 1;
X = v[s.at(i)][X];
}
return v;
}
};
|
Accepted
74/74 cases passed (48 ms)
Your runtime beats 20.02 % of cpp submissions
Your memory usage beats 5.02 % of cpp submissions (30.6 MB)
😜km
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int strStr(string haystack, string needle) {
vector<int> right(256, -1);
for(int i = 0; i < needle.size(); ++i)
{
right[needle.at(i)] = i;
}
int skip = 0;
int M = haystack.size();
int N = needle.size();
int j;
for(int i = 0; i <= M -N; i += skip) {
for( j = N - 1; j >= 0; --j) {
if(needle[j] != haystack[i + j]) {
skip = j - right[needle[j]];
if(skip < 1) skip = 1;
break;
}
}
if(j == -1) return i;
}
return -1;
}
};
|
Accepted
74/74 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 11.13 % of cpp submissions (9.4 MB)
