字符串查找是经典场景，也是面试中最常见的一道题。
说来惭愧，毕业3年了，才明白了kmp算法的实现，以前一直以为这类算法是基础，工作中中不会碰到【也的确没有碰到过。。。】
但是，对这些基本算法结构的理解是做一个工程师最基本的技能，好好学习，天天向上，在年前项目停止打酱油的日子里，敲了个bf和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 |
#include <stdio.h>#include <stdlib.h>#include <string.h>int
bf(char
*s, char* p) { int
i, j; int
lens,lenp; if(NULL == s || NULL == p) { return
-1; } lens = strlen(s); lenp = strlen(p); for(i = 0; i < lens; i++) { j = 0; while(s[i] == p[j] && j < lenp) { i ++; j ++; } if(j == lenp) { return
i - lenp; } i = i - j + 1; } return
-1;}int
main() { int
ret; char
s[] = "abcdhelloadf"; char
p[] = "hello"; ret = bf(s, p); printf("%d", ret); return
0;} |
|
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
72
73
74
75
76
77
78
79
80
81 |
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 100char
s[MAXN] = "ababaababcaba";char
p[MAXN] = "ababc";int
next[MAXN];int
kmp(char
*s, char
*p) { int
i, j; int
lens, lenp; if( NULL == s || NULL == p) { return
-1; } lens = strlen(s); lenp = strlen(p); for(i = 0; i < lens; i++) { j = 0; while(s[i] == p[j] && j < lenp) { i ++; j ++; } if( j == lenp) { return
i - j; } if(next[j] != -1){ j = next[j]; } else
{ j = 0; i ++; } } return
-1;}void
get_next(char
*p, int
*next) { int
i, j; int
len; int
tmp; len = strlen(p); for(i = 0; i < len; i++) { if(i == 0) { next[i] = -1; } else
if(i == 1) { next[i] = 0; } else
{ tmp = i - 1; for(j = tmp; j >= 0; j--) { if(equal(p, i, j)) { next[i] = j; break; } } } }}int
equal(char
*p, int
i, int
j) { int
tmpi; for(tmpi = 0; tmpi < j; tmpi++) { if(p[tmpi] != p[i, i - j + tmpi]) { return
0; } } return
1;}int
main() { int
lenp; int
ret; get_next(p, next); ret = kmp(s, p); printf("%d\n", ret); return
0;} |
原文：http://www.cnblogs.com/igloo1986/p/3534309.html