序 字符串T = abcabaabaadac, 字符串P = abaa,判斷P是否是T的子串，就是字符串匹配問題了，T叫做文本(Text),P叫做模式(Pattern). 算法思想 樸素的字符串匹配過程可以形象的看成一個包含模式的“模板”P沿文本T移動，同時對每個位移注意模板上的字符是否與文本中的相應字符相等。外層循環的次數最多為len(s) - len(p),內層循環的次數最多為len(p). 最壞情況下的時間復雜度：O((len(T) - len(P) + 1) * len(P)) 兩個for循環，代碼比較簡單，但是效率很低 算法代碼 [cpp] #include <stdio.h> #include <stdlib.h> #include <string.h> void main() { char part[20], str[50]; int i, flag, j, len_p, len_s, k; while(scanf("%s %s", part, str) != EOF) { //獲取字符串長度 len_p = strlen(part); len_s = strlen(str); //樸素字符串匹配算法 for(i = 0, flag = 0; i < len_s - len_p + 1; i ++) { for(j = i, k = 0; part[k] == str[j] && part[k] != '\0' && str[k] != '\0'; j ++, k ++) { } if(k > 0 && part[k] == '\0') { flag = 1; break; } http:// } //輸出匹配成功or失敗 if(flag) printf("匹配成功,匹配位置是:%d\n", i + 1); else printf("匹配失敗!\n"); } } 算法記號與術語 用 Σ* 表示用字母表Σ中的所有有限長度的字符串的集合 字符串x的長度用|x|表示 x和y的連接表示為xy,長度為|x| + |y| x = yw, y是x的前綴，w是x的後綴
