字符串匹配算法的C语言实现-算法导论第三版(1)

浏览数：17 / 时间：2015年06月08日

因为最近准备开始学习做一些小的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
输出 ： 指向目标字符数组的首地址的指针

测试用例：

技术分享