字符串匹配算法的C/C++实现-算法导论

因为最近准备开始学习做一些小的Android项目练手，看上了系统级的三个应用，拨号盘，通讯录和短信，准备从最简单的拨号做起，但是因为这些应用中都不可避免的会有自动提示，我觉得设计到的就是字符串匹配问题，这里准备使用C语言来实现，将来通过JNI集成到应用当中。

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（虽然理解起来不太容易）。