-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathstrStr.KMP.cpp
More file actions
71 lines (71 loc) · 1.7 KB
/
strStr.KMP.cpp
File metadata and controls
71 lines (71 loc) · 1.7 KB
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
strStr
Returns the position of the first
occurrence of string target in string source,
or -1 if target is not part of source.
int strStr(String source, String target) {
//…
}
//http://lintcode.com/problem/strstr/
*/
class Solution {
public:
/**
* Returns a index to the first occurrence of target in source,
* or -1 if target is not part of source.
* @param source string to be scanned.
* @param target string containing the sequence of characters to match.
*/
int strStr(const char *source, const char *target) {
if (source == NULL || target == NULL) {
return -1;
}
return kmp(string(source), string(target));
}
private:
void makeNext(const string target, vector<int> &next) {
int len = target.size();
if (len == 0) {
return;
}
next[0] = 0;
int k = 0;
for (int i = 1; i < len; ++i) {
while (k > 0 && target[i] != target[k]) {
k = next[k - 1];
}
if (target[i] == target[k]) {
++k;
}
next[i] = k;
}
}
int kmp(const string source, const string target) {
if (source.size() == 0) {
if (target.size() == 0) {
return 0;
}
else {
return -1;
}
}
if (target.size() == 0) {
return 0;
}
int len = source.size(), k = 0;
vector<int> next(target.size());
makeNext(target, next);
for (int i = 0; i < len; ++i) {
while (k > 0 && source[i] != target[k]) {
k = next[k - 1];
}
if (source[i] == target[k]) {
++k;
}
if (k == target.size()) {
return i - k + 1;
}
}
return -1;
}
};