在長度為n的數組T[n]中查找一個長度為m的數組P[m],如果用樸素字符串匹配方法要用O(mn)的時間，用自動機匹配要O(n)的時間，但一般的自動機要O(ml)的時間(l為字符集的寬度),而KMP只要O(m)的預處理時間。

其實最早接觸字符串匹配自動機應該是在數字電路中的序列檢測器那時候，序列檢測器是用硬件區實現一個個狀態的轉換，這里和那兒是一個原理。主程序維持一個狀態量mode是在讀入某個字符后的匹配長度，它隨著繼續讀入字符而不斷變化，而變化的函數可以由模式P[m]和字符集去確定，確定這個函數的時間可以為O(ml)（根據《算法導論》，但是我的程序都是O(m^3 * l)的，不知道他是怎么實現的)，以杭電1686題為例：

1 #include<stdio.h> 2 #include<string.h> 3 #include<memory.h> 4 5 #define MAXM 1000005 6 #define MAXN 10005 7 #define MAXW 26 8 9 char str[MAXM]; 10 char key[MAXN]; 11 int mode[MAXN][MAXW]; 12 13 int FINITE_AUTOMATION_MATCHER(); 14 void COMPUTE_TRANSITION_FUNCTION(); 15 16 int main() 17 { 18 //freopen("Sample Input.txt","r",stdin); 19 int T; 20 scanf("%d",&T); 21 22 while(T--) 23 { 24 scanf("%s%s",key,str); 25 printf("%d\n",FINITE_AUTOMATION_MATCHER()); 26 } 27 28 return 0; 29 } 30 31 int FINITE_AUTOMATION_MATCHER() 32 { 33 int len1 = strlen(str); 34 int len2 = strlen(key); 35 int cnt = 0; 36 int cur_mode = 0; 37 38 memset(mode,0,sizeof(mode)); 39 COMPUTE_TRANSITION_FUNCTION(); 40 41 for(int i = 0;i < len1;i++) 42 { 43 cur_mode = mode[cur_mode][str[i] - 'A']; 44 cnt = cur_mode == len2 ? cnt + 1 : cnt; 45 } 46 47 return cnt; 48 } 49 50 51 void COMPUTE_TRANSITION_FUNCTION() //四層循環求轉換函數，O(m^3 * l)的復雜度 52 { 53 int len = strlen(key); 54 55 for(int i = 0;i <= len;i++) 56 { 57 for(int j = 0;j < 26;j++) //寫的有點倉促，很亂。。。。 58 { 59 int k = i + 1 > len ? len : i + 1; 60 int flag = 0; 61 62 for(;k > 0;k--) 63 { 64 flag = 1; 65 66 if(key[k - 1] - 'A' != j) 67 { 68 continue; 69 } 70 71 for(int s = 0;s < k - 1 && flag;s++) 72 { 73 flag = key[s] == key[i - k + s + 1] ? 1 : 0; 74 } 75 76 if(flag) 77 { 78 break; 79 } 80 } 81 mode[i][j] = k; 82 } 83 } 84 } 85 86 87 88 89 90 普通的自動機由于轉移函數耗時太長TL了。KMP算法類似于自動機它也維持一個暫時的匹配長度mode，在讀入下一個字符時如果匹配不成功，那么就要減小mode，求減小的量(前綴函數)就是KMP的核心。前綴函數f[i]是滿足是模式P[i]的真后綴和前綴的最大長度，算法中求前綴函數的過程就是模式自己和自己匹配的過程，f[i]就是在讀入第i個字符時和模式P的最大匹配長度，因此求前綴函數的過程和匹配過程高度相似，下面還是以hdu1686題為例： 91 92 #include<stdio.h> 93 #include<string.h> 94 #include<memory.h> 95 96 #define MAXM 1000005 97 #define MAXN 10005 98 99 char str[MAXM]; 100 char key[MAXN]; 101 int mode[MAXN]; 102 103 int KMP_MATCHER(); 104 void COMPUTE_PREFIX_FUNCTION(); 105 106 int main() 107 { 108 //freopen("Sample Input.txt","r",stdin); 109 int T; 110 scanf("%d",&T); 111 112 while(T--) 113 { 114 scanf("%s%s",key,str); 115 printf("%d\n",KMP_MATCHER()); 116 } 117 118 return 0; 119 } 120 121 int KMP_MATCHER() 122 { 123 int cnt = 0; 124 int cur_mode = 0; //相當于自動機中的狀態 125 int len1 = strlen(str); 126 int len2 = strlen(key); 127 128 memset(mode,0,sizeof(mode)); 129 COMPUTE_PREFIX_FUNCTION(); 130 131 for(int i = 0;i < len1;i++) 132 { 133 while(cur_mode > 0 && key[cur_mode] != str[i]) 134 { 135 cur_mode = mode[cur_mode]; 136 } 137 138 if(key[cur_mode] == str[i]) 139 { 140 cur_mode++; 141 } 142 143 if(cur_mode == len2) 144 { 145 cnt++; 146 } 147 } 148 149 return cnt; 150 } 151 152 void COMPUTE_PREFIX_FUNCTION() //自己和自己匹配的過程 153 { 154 mode[1] = 0; 155 156 int k = 0; //已匹配長度 157 158 for(int i = 2;i <= strlen(key);i++) 159 { 160 while(k > 0 && key[k] != key[i - 1]) 161 { 162 k = mode[k]; 163 } 164 165 if(key[k] == key[i - 1]) 166 { 167 k++; 168 } 169 170 mode[i] = k; 171 } 172 } 173 174 //7738004 2013-03-11 19:14:48 Accepted 1686 671MS 1268K 1152 B G++ 超級旅行者

?

算法還是不夠快，功力尚淺啊，還需修煉，看看有沒有更快的算法。

參考文獻：《算法導論》

?

轉載于:https://www.cnblogs.com/codingMozart/archive/2013/03/11/6439749.html

總結

以上是生活随笔為你收集整理的字符串匹配自动机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。