Liny_@NotePad

沉迷ACG中

字符串匹配的RK算法+随机

YOYO posted @ 2009年6月10日 03:14 in 【算法】与【数据结构】 with tags RK 字符串匹配 随机 , 3600 阅读

在使用RK算法进行字符串匹配时,q必须是一个充分大的素数。为了减少出现假匹配的概率,先计算小于12mn2的素数集合,再从集合中随机取出一个素数,可使假匹配的概率小于1/n。此外,这个算法总能得到正确的答案。

  1. #include<iostream>
  2. #include<map>
  3. #include<set>
  4. #include<time.h>
  5. using namespace std;
  6.  
  7. #define N 100   // 待匹配串的最多长度
  8. #define M 20    //  模式串的最多长度
  9.  
  10. #define MULTIPLIER 0x015A4E35L
  11. #define INCREMENT 1
  12.  
  13. static unsigned long seed;
  14.  
  15. /*      生成随机数种子 */
  16. void random_seed(unsigned long d){
  17.         if(d==0){
  18.                 seed = time(0);
  19.         }else{
  20.                 seed = d;
  21.         }
  22. }
  23.  
  24. /*      生成一个low~high范围内的随机数 */
  25. unsigned int random(unsigned long low, unsigned long high){
  26.         seed = MULTIPLIER * seed + INCREMENT;
  27.         return ((seed>>16)%(high-low)+low);
  28. }
  29.  
  30. long BASE;                  //    进制数
  31. set<char> v;        //  存放待匹配串和模式串中出现的字符的集合
  32. map<char, int>data;     //   存放待匹配串和模式串中出现的字符的哈希表
  33.  
  34. /*      将串中出现的字符放入集合 */
  35. void inSet(char s[]){
  36.         int n = strlen(s);
  37.  
  38.         for(int i = 0; i<n; i++){
  39.                 v.insert(s[i]);
  40.         }
  41.  
  42.         BASE = v.size();
  43. }
  44.  
  45. /*      计算出现的字符的哈希表 */
  46. void countMap(){
  47.         data.clear();
  48.         int i = 0;
  49.         for(set<char>::iterator iter = v.begin(); iter!=v.end(); iter++){
  50.                 data[*iter] = i++;
  51.         }
  52. }
  53.  
  54. /*      出现的字符的哈希函数 */
  55. int ch(char s){
  56.         return data[s];
  57. }
  58.  
  59. /*
  60. * 字符串匹配
  61. * 输入:存放待匹配串的数组S[],待匹配串的长度n,
  62. *             存放模式串的数组P[],模式串的长度m,素数p
  63. * 输出:与P相匹配的子串在待匹配串中的起始位置loc
  64. */
  65. void match(char S[], long n, char P[], long m, long &loc, long q){
  66.         long b = BASE;
  67.         long i, k;
  68.         long w = 0, p = 0;
  69.         long x = 1;
  70.  
  71.         //      计算b^(m-1) % q
  72.         for(i=0; i<m-1; i++){
  73.                 x = (x*b)%q;
  74.         }
  75.  
  76.         //      计算第一个窗口子串的哈希值
  77.         for(i=0; i<m; i++){
  78.                 w = (w*b + ch(S[i]))%q;
  79.         }
  80.  
  81.         //      计算模式串的哈希值
  82.         for(i=0; i<m; i++){
  83.                 p = (p*b + ch(P[i]))%q;
  84.         }
  85.  
  86.         i = 0;
  87.         while((i<=n-m) && (loc == -1)){
  88.                 if(w==p) {      //    如果与模式串相等 则仔细检查是否真的相等
  89.                         for( k=0; k<m; k++){
  90.                                 if(S[i+k]!=P[k])break;
  91.                         }
  92.                         if(k>=m) loc = i;
  93.                 }
  94.                 //      计算下一个窗口子串的哈希值
  95.                 w = w - ch(S[i])*x%q;
  96.                 if(w<0) w += q;
  97.                 w = (w*b + ch(S[i+m]))%q;
  98.                 i++;
  99.         }
  100. }
  101.  
  102. /*
  103. * 字符串匹配的随机算法
  104. * 输入:存放待匹配串的数组S[],待匹配串的长度n,
  105. *             存放模式串的数组P[],模式串的长度m,
  106. *             小于12*m*n*n的素数集合R[],素数集合的元素个数a
  107. * 输出:与P相匹配的子串在待匹配串中的起始位置loc
  108. */
  109. void match_random(char S[], long n, char P[], long m, long &loc, long R[], int a){
  110.         long q;
  111.         random_seed(0);
  112.         q = random(a/2,a);      //    从a/2~a范围中取一个素数
  113.         q = R[q];
  114.         match(S, n, P, m, loc, q);
  115. }
  116.  
  117. /*
  118. * 找素数算法
  119. * 输入:所找素数的上界size
  120. * 输出:所找素数集合的大小a
  121. */
  122. long* findPrime(int size, int &a){
  123.         long* r = new long[size];
  124.         bool* prime = new bool[size];
  125.        
  126.         int i,j;
  127.         prime[0] = false;
  128.         for(i=1; i<size; i++){
  129.                 prime[i] = true;
  130.         }
  131.  
  132.         i = 1;
  133.         while(i<size){
  134.                 if(prime[i]){
  135.                         j = (i+1)*2;
  136.                         while(j<size){
  137.                                 prime[j-1] = false;
  138.                                 j += i+1;
  139.                         }
  140.                 }
  141.                 i++;
  142.         }
  143.  
  144.         a = 0;
  145.         for(i=1; i<size; i++){
  146.                 if(prime[i-1]){
  147.                         r[a++] = i;
  148.                 }
  149.         }
  150.  
  151.         delete prime;
  152.  
  153.         return r;
  154. }
  155.  
  156. int main(){
  157.         char str[N], substr[M];
  158.  
  159.         while(cin>>str){
  160.                 if(!strcmp(str,"exit"))break;   // 待匹配串为exit时退出
  161.                 cin>>substr;
  162.  
  163.                 long loc = -1;
  164.                 int n = strlen(str);
  165.                 int m = strlen(substr);
  166.                 int a;
  167.                 long* R = findPrime(12*m*n*n, a);       //     计算小于12*m*n*n的素数集合
  168.  
  169.                 /* 计算待匹配串和模式串中出现的元素集合 */
  170.                 v.clear();
  171.                 inSet(str);
  172.                 inSet(substr);
  173.                 countMap();
  174.  
  175.                 //      随机匹配
  176.                 match_random(str, n, substr, m, loc, R, a);
  177.  
  178.                 if(loc==-1){    //  如果未匹配 则尝试用最接近12*m*n*n的素数进行匹配
  179.                         cout<<"No Found!"<<endl;
  180.                         match(str, n, substr, m, loc, R[a-1]);
  181.                         cout<<"Use Prime: "<<R[a-1]<<endl;
  182.                         if(loc==-1){
  183.                                 cout<<"No Found!"<<endl;
  184.                         }else{
  185.                                 cout<<"Location In "<<loc+1<<endl;
  186.                         }
  187.                 }else{
  188.                         cout<<"Location In "<<loc+1<<endl;
  189.                 }
  190.  
  191.                 delete R;
  192.                
  193.                 system("pause");
  194.                 cout<<"================================"<<endl;
  195.         }
  196.  
  197.         return 0;
  198. }

才知道%对负数不起作用……还需要自己手工判断……


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter