字符串匹配算法(一)——朴素算法

写python代码写习惯了,再来用C代码处理字符串感觉很痛苦。在python中有find、index等函数可以进行字符串匹配,而用C语言就只能自己写了。

朴素算法思路比较简单,就是将源字符串与目标字符串挨个进行比较,看看在目标字符串中是否包含了源字符串。该算法的匹配时间为O((n-m+1)m)。

C语言实现如下:

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
#include <stdio.h>
int native_matcher(char *t, char *p, int len1, int len2)
{
int i, j, idx;
idx = 0;
for (i=0; i<len1; i++) {
for (j=0; j<len2; j++) {
if (p[j] != t[j+i]) {
break;
}
}
if (j == len2) {
return i;
}
}
return -1;
}
int main(int argc, char *argv[])
{
char t[] = "BBC ABCDAB ABCDABCDABDE";
char p[] = "ABCDABD";
int len1 = sizeof(t) - 1;
int len2 = sizeof(p) - 1;
int index = native_matcher(t, p, len1, len2);
printf("index: %d\n", index);
return 0;
}