本来想用kmp但是getnext写出来太扯淡超时。
最近真心累了，暂停一段时间吧。用朴素的模式匹配过了。
隔断时间再练习，最近看看里奇的原版C程序设计语言和深入理解计算机系统吧。真心累了，压力还大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int lenh = strlen(haystack);
int lenn = strlen(needle);
if(lenh == 0 && lenn == 0)return haystack;
for(int i = 0;i < lenh;i++) {
if(strlen(haystack + i) >= lenn&&isEqual(haystack,i,needle))return haystack + i;
}
return NULL;
}
private:
bool isEqual(char *haystack,int i,char * needle) {
int j;
for(j = 0;j < strlen(needle);j++) {
if(needle[j] != haystack[i+j])break;
}
if(j == strlen(needle))return true;
else return false;
}
};
|
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
29
30
31
32
33
34
35
36
37
38
39
40
41
|
class Solution {
public:
int lenh;
int lenn;
int *next;
char *strStr(char *haystack, char *needle) {
lenh = strlen(haystack);
lenn = strlen(needle);
if(lenn == 0)return haystack;
if(lenh < lenn)return NULL;
next = new int[lenn];
getNext(needle);
int k = 0;
int j = 0;
while(j < lenh) {
if(k == -1 || needle[k] == haystack[j]) {
k++;
j++;
if(k == lenn)return haystack + j - lenn;
}
else
k = next[k];
}
return NULL;
}
private:
void getNext(char *needle) {
int k = -1;
int j = 0;
next[j] = k;
while(j < lenn-1) {
if(k == -1 || needle[k] == needle[j]) {
k++;
j++;
next[j] = k;
}
else
k = next[k];
}
}
};
|