因為最近准備開始學習做一些小的Android項目練手，看上了系統級的三個應用，撥號盤，通訊錄和短信，准備從最簡單的撥號做起，但是因為這些應用中都不可避免的會有自動提示，我覺得設計到的就是字符串匹配問題，這裡准備使用C語言來實現，將來通過JNI集成到應用當中。
算法導論 原書第2版 高清PDF及答案 下載 http://www.linuxidc.com/Linux/2015-05/117756.htm
1.首先是樸素匹配，實際上就是窮舉：
用C語言實現的函數我放到這裡：
1 void naive_string_match(char *t,char *p){
2 int n = strlen(t);
3 int m = strlen(p);
4 int s;
5 for(s=0;s<=n-m;++s){
6 if(!strncmp(p,t+s,m)){
7 printf("OK , %d",s);
8 }
9 }
10 }
（注意，為了方便將來移植，我的實現中所有函數都是被包含在POSIX的標准中的）
這裡說明上面兩個我不熟悉的方法
1.strlen(string.h) 計算字符串長度 傳入 ： 一個指向C類型字符串(char */char [])的指針 返回 ： 不含\0的字符串長度 2.strncmp(string.h) 比較兩個字符串前n個字符是否相同 傳入 ： 兩個要比較的字符串，還有n 返回 ： 相同返回0，不同則根據情況返回其他值
2.Rabin-Karp算法
基本數論的概念不太懂，但是簡單實現還是可以的，
因為此算法描述比較針對數字字符串進行匹配，我的實現主要就是針對手機號之類的數字來進行匹配，當然，具體描述還要看算法導論上的描述
（1）秦九韶/horner法則
1 int horner(char *p,int d,int m){
2 int result = 0;
3 int i;
4
5 for(i=0;i<m-1;++i){
6 result = ((p[i]-48) + result)*d;
7 }
8
9 result+=(p[m-1]-48);
10 return result;
11 }
（2）按照偏移量計算t的字串的數值大小
1 int* cal(char *t,int m,int d){
2 int i;
3 int sub = strlen(t) - m;
4 char *tmp = (char *)malloc(m * sizeof(char) + 1);
5 int *result = (int *)malloc((sub + 1) * sizeof(int));
6
7 tmp = strncpy(tmp,t,m);
8 result[0]=horner(tmp,d,m);
9
10 for(i=1;i<sub+1;++i){
11 result[i] = (result[i-1] - pow(d,m-1) * (t[i-1] - 48))*d + (t[i-1+m]-48);
12 }
13
14 free(tmp);
15 return result;
16 }
注意，其中的pow函數是自己寫的一個簡單函數而不是math.h中的函數：
1 int pow(int d,int m){
2 int result=1;
3 while(m>0){
4 result *= d;
5 --m;
6 }
7 return result;
8 }
（3）主算法：
1 void rabin_karp_matcher(char *t,char *p,int d,int q){
2 int s,i,c;
3 int m=strlen(p);
4 int n=strlen(t);
5
6 int px=horner(p,d,strlen(p)) % q;
7 int *tx=cal(t,m,d);
8
9 c=n - m + 1;
10
11 for(i=0;i<c;++i){
12 tx[i] %= q;
13 }
14
15 for(s=0;s<c;++s){
16 if(px==tx[s]){
17 if(!strncmp(p,t+s,m)){
18 printf("OK , %d\n",s);
19 }
20 }
21 }
22
23 free(tx);
24 }
（注意，tx的位置是我之前分配的空間，所以用完之後還是free掉為好）
下面是我在實現上述代碼過程中不熟悉的一個函數描述：
3.strncpy(string.h) 將一個字符串的前m個字符復制到另外一個字符數組（必須至少比m大一個\0的存儲位置）中（注意：這裡最後一個位必須考慮進去，但是在按照%s輸出目標字符數組的時候，在Windows上顯示最後一位是‘?’） 傳入 ： 目標字符數組，原字符數組，計數m 輸出 ： 指向目標字符數組的首地址的指針
測試用例：
（不出意外，這個就是我用來做撥號盤的匹配的算法了）
3.基於有限自動機的字符串匹配算法
這個自動機算法算是比較好理解的一個算法，因為我學過數字邏輯，課上有講過有限自動機的原理，所謂有限自動機，就是在系統在有限情況下，任何狀態的變化都在系統的有效循環內，在系統當前狀態下，系統針對任意一個可預知的輸入（比如我們知道系統輸入只可能是0或1），都有一個有效的狀態轉移。
具體理論還請自行翻書，下面是我的實現，由於在構造狀態轉移函數的時候我沒有自定義數據結構，而是選擇了C++的map類型來存儲的轉移函數，所以下面使用的都是C++的基本語法，使用了auto表明我使用了C++11標准，Android NDK應該是支持的，下面是具體實現：
1.計算狀態轉移函數
1 map<int, map<char, int>> compute_transition_function(const string &P, const string &ALL){
2 map<int, map<char, int>> delta;
3 map<char, int> item;
4 int m = P.length();
5 for (int q = 0; q <= m; ++q){
6 for (auto &a : ALL){
7 string dest = P.substr(0, q) + a;
8 string src;
9 int k = min(m + 1, q + 2);
10 do{
11 --k;
12 src = P.substr(0, k);
13 if (src == ""){
14 break;
15 }
16 } while (src != dest.substr(dest.length() - src.length(), dest.length()));
17 item.insert(make_pair(a, k));
18 }
19 delta.insert(make_pair(q, item));
20 item.clear();
21 }
22 return delta;
23 }
2.根據狀態轉移表來進行匹配：
1 void finite_automation_matcher(const string &T, const map<int, map<char, int>> &delta,const int &m){
2 int n = T.length();
3 int q = 0;
4 for (int i = 0; i < n; ++i){
5 q = (delta.at(q)).at(T[i]);
6 if (q == m){
7 cout << "Match " << i - m + 2 << endl;
8 }
9 }
10 }
這裡我在map中查找的方法可能不是很正規，有好的方法請告訴我。
測試書中的用例的結果：
記錄下上述我不熟悉的函數：
4.substr(string) 返回一個字符串特定范圍(m,n）內的字符串，就是按需返回子字符串的一個string對象的方法 對象類型 ： string 輸入 ： (m,n) 字串范圍，從m位置開始，到n位置結束，不包含n位置的字符 輸出 ： 子串，也是一個string對象
4.KMP算法
在有限自動機的基礎上，KMP是針對要匹配的字符串進行再次優化的一種方式。
因為有限自動機針對的是每個要匹配的字符串中的字符計算的轉移函數。而KMP則是針對要匹配的字符串的字串來減少比較計算的。
比如ababaca這裡，發現如果目標字符串與要匹配的字符串中的前5個字符匹配，那麼如果根據樸素（窮舉）法，我們只能後移一位來繼續逐位比較，
但是可以看到的是，前五個字符的前兩個字符正好是他自己的後綴，
這樣，我們只需要將這兩個作為已經匹配好的字符串，同時計算好此時在樸素法中的相對位移，那麼就可以節約一大部分的比較時間。
使用KMP，需要計算出匹配字符串本身的“轉移函數”-後綴轉移函數（模式的前綴函數），這個函數記錄的是匹配字符串的前n個字符是前m個字符的後綴（m>n），因此，這個函數可以用一個映射來表示，同時每個m唯一（因為m是從0-匹配字符串長度的單步遞增,step=1）。
計算前綴函數的函數：
1 map<int, int> compute_prefix_function(const string &P){
2 int m = P.length();
3 map<int, int> pi;
4 int k = 0;
5
6 pi.insert(make_pair(1, 0));
7 for (int q = 1; q < m; ++q){
8 while (k > 0 && P[k] != P[q]){
9 k = pi.at(k);
10 }
11 if (P[k] == P[q]){
12 ++k;
13 }
14 pi.insert(make_pair(q+1, k));
15 }
16
17 return pi;
18 }
因為KMP很像樸素法，所以主算法中使用的就是結合前綴函數的一個類樸素匹配：
1 void kmp_matcher(const string &T, const string &P){
2 int n = T.length();
3 int m = P.length();
4 map<int, int> pi;
5 int q = 0;
6
7 pi = compute_prefix_function(P);
8 for (int i = 0; i < n; ++i){
9 while (q>0 && P[q] != T[i]){
10 q = pi.at(q);
11 }
12 if (P[q] == T[i]){
13 ++q;
14 }
15 if (q == m){
16 cout << "matcher at " << i - m + 2 << endl;
17 q = pi.at(q);
18 }
19 }
20 }
（為了好看，我輸出改成了i-m+2，這裡隨便我們寫）.
測試書中示例的結果：
以上就是算法導論中主要介紹的字符串匹配算法，如果匹配大規模字符串，當然建議是KMP（雖然理解起來不太容易）。
