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 閱讀(3222)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎