字符匹配问题（1）――Rabin-Karp算法

字符串匹配问题（ 1 ）—— Rabin-Karp 算法

1.       问题描述

给定目标字符串 T[0..n-1] （基于 0 的数组，数组长度为 n ），和模式串 P[0..m-1] ，问 P 可否匹配 T 中的任意子串，如果可以，返回匹配位置。

2.       问题分析

            直观分析

brute-force 的蛮力法，适用于较小规模的字符串匹配。

            优化

主要介绍 3 种优化办法，分别具体为： Rabin-Karp 算法，有限自动机和 KMP 算法。将分为 3 篇博文分别讨论。本小节主要介绍 Rabin-Karp 算法。

            得出算法

Rabin-Karp 算法（以下简称为 RK 算法），是基于这样的思路：即把串看作是字符集长度进制的数，由数的比较得出字符串的比较结果。例如，给定字符集为∑ ={0,1,2,3,4,5,6,7,8,9} ，∑长度为 d=10 ，那么任何以∑为字符集的串都可看作 d （此处为 10 ）进制的数。

记模式串 P[0..n-1] 对应的数值为 P ， T[0..n-1] 所有长度为 m 的子串对应的数值为 t_s ，设 P 和 T 都是基于字符集长度为 | ∑ |=d 的字符串。

那么， t_s 即为 T[s..s+m] 对应的数值，这里 0<=s<=n-m-1 。

P = P[m]+d*(P[m-1]+d*(P[m-2]+..)))

同样 t₀ 也可类似求得。

最重要的是如何从 t_s 求出 t_s+1 。

t_s+1 =T[s+m]+d*(t_s +d^m-1 *T[s])

注：此处是该算法的关键，即在常数时间内能够计算出下一个 m 长度的字串对应的数值。初看比较抽象，举个例子就比较明白了，设 x=12345 ，现在是已知长度为 3 的数值 234 ，现在要求 345 对应的数值，可以这样来得到： 345 = 5 + 10*(234-10² *2)

3.       算法描述

求出所有 m 长度子串所对应的数值，对数值进行比较，继而得出子串是否匹配。当模式串长度很大时，这时对应的数值会很大，比较起来比较麻烦，可使用对一个大奇数取模后进行比较。

4.       具体实现

       这里实现的只是m值较小时的情形，大整数需要特定的类的支持（如可自定义大整数类），选取10进制的数是为了方便起见，当然字母也是OK的。

Cpp代码

1. #include "iostream"  
2. #include "string"  
3. #include "cmath"  
4. using namespace std;  
5.   
6. // get the value of the character in the set   
7. int getV(char p, string set)  
8. {  
9.     for(int i=0; i<set.length(); i++)  
10.     {  
11.         if (p==set[i])  
12.             return i;  
13.     }  
14.     return -1;  
15. }  
16. // d is the size of the character set  
17. int RK(string T, string P,string set)  
18. {  
19.     int d = int(set.length());  
20.     int n = T.length();  
21.     int m = P.length();  
22.     int h = pow(double(d), m-1);  
23.     int p=0;  
24.     int t = 0;  
25.     for(int i=0; i<m; i++)  
26.     {  
27.         p = d*p + getV(P[i],set);  
28.         t = d*t + getV(T[i], set);  
29.     }  
30.     for (int s=0; s<=n-m; s++)  
31.     {  
32.         cout<<"p,t is "<<p<<","<<t<<endl;  
33.         if (p==t)  
34.             return s;  
35.         if (s<n-m)  
36.             t = getV(T[s+m],set)+d*(t-h*getV(T[s],set));  
37.     }  
38.     return -1;  
39. }  
40. int main()  
41. {  
42.     // set is the character set  
43.     string set= "0123456789";  
44.     // pattern P  
45.     string P = "2365";  
46.     // T is the string to match  
47.     string T = "258569236589780";  
48.     int i = RK(T, P, set);  
49.     cout<<"the postition is:"<<i<<endl;  
50.     return 0;  
51. }  

#include "iostream" #include "string" #include "cmath" using namespace std;  // get the value of the character in the set  int getV(char p, string set) {  for(int i=0; i<set.length(); i++)  {   if (p==set[i])    return i;  }  return -1; } // d is the size of the character set int RK(string T, string P,string set) {  int d = int(set.length());  int n = T.length();  int m = P.length();  int h = pow(double(d), m-1);  int p=0;  int t = 0;  for(int i=0; i<m; i++)  {   p = d*p + getV(P[i],set);   t = d*t + getV(T[i], set);  }  for (int s=0; s<=n-m; s++)  {   cout<<"p,t is "<<p<<","<<t<<endl;   if (p==t)    return s;   if (s<n-m)    t = getV(T[s+m],set)+d*(t-h*getV(T[s],set));  }  return -1; } int main() {  // set is the character set  string set= "0123456789";  // pattern P  string P = "2365";  // T is the string to match  string T = "258569236589780";  int i = RK(T, P, set);  cout<<"the postition is:"<<i<<endl;  return 0; } 

 

  5.       参考资料

[1]   Thomas H. Cormen Introduction to Algorithms

C 语言中字符数组的存储

程序片段 :

C代码

1. void mstrcat(char *s, char *t)  
2.   
3. {  
4.   
5.          s += strlen(s);  
6.   
7.          for(;*t!='\0';*s++=*t++);  
8.   
9.          *s = '\0';  
10.   
11. }  

void mstrcat(char *s, char *t)  {           s += strlen(s);           for(;*t!='\0';*s++=*t++);           *s = '\0';  }

 

这是一个字符数组连接的函数 .

(一)在测试程序中声明如下 :

C代码

1. char a[] = "abcd";  
2. char b[] = "ef";  
3. char s[] = "ghijklmnopqrstuvwxyz";  
4. char *c;  
5. char *d;  
6.   
7. mstrcat(b, s);  
8. /* 连接后的b */  
9. printf("after:%s\n", b);  
10. /* a */  
11. printf("after:%s\n", a);  
12. /* 各字符数组的首元素地址  */  
13. printf("%d\n", (int)a);  
14. printf("%d\n", (int)b);  
15. printf("%d\n", (int)s);  

char a[] = "abcd"; char b[] = "ef"; char s[] = "ghijklmnopqrstuvwxyz"; char *c; char *d;  mstrcat(b, s); /* 连接后的b */ printf("after:%s\n", b); /* a */ printf("after:%s\n", a); /* 各字符数组的首元素地址  */ printf("%d\n", (int)a); printf("%d\n", (int)b); printf("%d\n", (int)s);

 分别在GCC3.4.4和VC6.0后,得出2种不同的结果:
GCC:
after:efghijklmnopqrstuvwxyz
after:uvwxyz
22ccd0
22ccc0
22cca0
得出结论(无异常产生):
每个字符按一个字节存储,并且相邻字符数组按照地址下降来存储,而一个数组内元素按照地址上升来存储.
GCC依照16个字节对齐原则进行对齐处理(即不足16个字节的数组,按16个字节进行对齐存储)


VC6.0:(出现异常)
after:efghijklmnopqrstuvwxyz
after:ijklmnopqrstuvwxyz
1245048
1245044
1245020

得出的结论:
VC6.0:
每个字符按一个字节存储,并且相邻字符数组按照地址下降来顺序存储 ,而一个数组内元素按照地址上升来存储.
VC6.0依照4个字节对齐原则进行对齐处理(即不足4个字节的数组,按4个字节进行对齐存储)

总结:
总之,这种处理方式是种不安全的处理方式,是否出现异常取决于是否有足够的已申请空间的支持.
在GCC中未出现异常是因为GCC按照16字节的对齐方式,即32字节足以容纳连接后的字符数组b.
而在VC中出现异常是因为VC按照4字节的对齐方式,4字节不能容纳b.
可预见的是:如果当b的字符数组长度大于32时,GCC中也会出现异常.

(二)在测试程序中声明如下 :

同样在测试程序中如果声明如下

C代码

1. char *c;  
2. char *d;  
3.   
4. c = "abcd";  
5. d = "efghi";  
6.   
7. printf("%d\n", (int)c);  
8. printf("%d\n", (int)d);  
9.   
10. mstrcat(c, d);  
11. printf("%s\n", c);  

char *c; char *d;  c = "abcd"; d = "efghi";  printf("%d\n", (int)c); printf("%d\n", (int)d);  mstrcat(c, d); printf("%s\n", c);

 那么,在GCC和VC(版本同上)中的结果如下:
GCC(出现异常):
402000
402005

得出结论:
对于未指定所指对象的指针,其地址是编译器任意指定的,而当指定其所指对象时,指针则存储的是所指对象的首地址(例如,指针c指向的是字符数 组"abcd"的首 地址),由于字符数组之间顺序存放,所以d指向的是5个字节("abcd"占用5个字节存储空间)后的位置,这里我们的看到的地址是升序的.


VC(出现异常):
4333604
4337624

得出结论:
对于VC而言,其相邻指定给指针的字符数组并非顺序存储,但指针指向的位置仍然是所指对象的首地址.
出现异常的原因是:
显然对于d字符数组所需要的连续存储空间c是不满足的(不能操作未申请的存储空间).

ps.
在(一)中,即使使用c语言的标准字符串函数strcat,strcat(b,s)也会出现异常,可见标准函数也没有使用重新申请新空间的方式处理.