KMP算法用来求解一个字符串是否是另外一个字符串的子串，算法复杂度为
θ(n)。
大致讲解下KMP算法的思想，这里不做深究，因为网上一搜一大片，尤其以Matrix67讲解的非常棒，可以参考：
http://www.matrix67.com/blog/archives/115
KMP的核心思想其实就是当在匹配的过程中，一旦发现当前字符mother[i]与child[j]不匹配，则将j向前移，而保持i不变，这样就能使得i始终是向后移动的，所以能保证时间复杂度为θ(n)。具体j应该如何移动，则需要预处理子串child，得出next数组，然后根据next数组查找j该向前移动多少步。这里的思想是如果当前mother[i] != child[j]，则应该使j = next[j]，然后继续匹配mother[i]与child[j]。next[j]的含义其实就是字符串0~next[j]是字符串0~j的后缀。理解了这个之后就可以看懂KMP代码了。
下面是实现代码，实现的比较丑陋，讲究看吧：
1 static int compute_next(const char *str, int *next, int len) {
2 if (!str || !next || len <= 0) {
3 return -1;
4 }
5 next[0] = -1;
6 int k = -1;
7 int i = 1;
8 for (i; i < len; ++i) {
9 while (k >= 0 && str[i] != str[k + 1]) {
10 k = next[k];
11 }
12 if (str[i] == str[k + 1]) {
13 k++;
14 }
15 next[i] = k;
16 }
17 return 0;
18 }
19
20 //KMP算法查找子串
21 char *Strstr(const char *str1, const char *str2) {
22 if (!str1 || !str2) {
23 return NULL;
24 }
25 int str1len = strlen(str1);
26 int str2len = strlen(str2);
27 int *next = (int *)malloc(sizeof(int) * str2len);
28
29 if (compute_next(str2, next, str2len) == -1) {
30 return NULL;
31 }
32
33 int k = -1;
34 int i = 0;
35 for (; i < str1len; ++i) {
36 while (k >= 0 && str1[i] != str2[k + 1]) {
37 k = next[k];
38 }
39 if (str1[i] == str2[k + 1]) {
40 k++;
41 }
42 if (k == str2len - 1) {
43 free(next);
44 next = NULL;
45 return str1 + i - str2len + 1;
46 }
47 }
48 free(next);
49 next = NULL;
50 return NULL;
51 }
poj1226题是典型的最长公共子串问题，题意是有若干个字符串，找出最长的一个子串的长度，该子串或者其反串是所有字符串的子串。数据比较弱，所以用strstr也可以ac。思想其实是找出这N个字符串中最短的串，假设其长度为l，然后依次枚举该串的子串，不过这里可以枚举子串的长度，从l开始枚举，一旦发现该串或者其反串是所有串的子串，则输出该长度。代码如下：
1 int main() {
2 int cases, n, min_len, min_len_index, i, j, k, index, flag;
3 char str_buf[105];
4 char rev_buf[105];
5 scanf("%d", &cases);
6 while (cases--) {
7 scanf("%d", &n);
8 if (!n) {continue;}
9 min_len = 105;
10 min_len_index = -1;
11 for (i = 0;i < n; ++i) {
12 scanf("%s", strings[i]);
13 string_len[i] = strlen(strings[i]);
14 if (string_len[i] < min_len) {
15 min_len = string_len[i];
16 min_len_index = i;
17 }
18 }
19
20 while (min_len) {
21 //枚举长度为min_len的子串
22 for (i = 0; i <= string_len[min_len_index] - min_len; ++i) {
23 for (index = 0, j = i; j < i + min_len; ++j, ++index) {
24 str_buf[index] = strings[min_len_index][j];
25 rev_buf[min_len - 1 - index] = strings[min_len_index][j];
26 }
27 str_buf[index] = '\0';
28 rev_buf[index] = '\0';
29 for (k = 1, flag = 1; k < n; ++k) {
30 if (!Strstr(strings[k], str_buf) && !Strstr(strings[k], rev_buf)) {
31 flag = 0;
32 break;
33 }
34 }
35 if (flag == 1) {
36 goto end;
37 }
38 }
39 min_len--;
40 }
41 end: printf("%d\n", min_len);
42 }
43 return 0;
44 }
posted on 2012-09-11 20:10
myjfm 阅读(3121)
评论(0) 编辑 收藏 引用 所属分类:
算法基础