字元串比對rk算法c語言,Chpt.6.字元串比對--算法6.6 RK算法(rkSM)

這是一個有個性的算法，他的兩位提出者都是Turing獎的獲得者.:)

基本的思想就是把字元串映射成一個函數值，指紋函數。Hash...

但是text太大的時候，預處理時間也是得考慮進來的~不過最壞的時候也就和平凡算法一樣了(還可能更壞嗎...)

#include #include #include

void usage(char * prog)

{

printf("Usage: %s text pattern\n", prog);

exit(123);

}

void rk_sm(char * patt, char * text, int patt_length, int text_length, int c, int q)

{

int p = 0, t = 0;

long long h = 1;

int     i, k, s;

int flag;

for(i = 0; i <= patt_length -1; i ++)

h *= c;

h = h % q;

for(i = 0; i < patt_length; i ++)

{

p = (c * p + patt[i])%q;

t = (c * t + text[i])%q;

}

for(s = 0; s < text_length - patt_length + 1; s ++)

{

if(p == t)

{

flag = 1;

for(i = 0; i < patt_length; i ++)

if(patt[i] != text[s+i])

flag = 0; //set flag, not match...

if(flag)

{

printf("position %d\n", s);

printf("text: %s\n", text);

printf("patn: ");

for(k = 1; k <= s; k ++)

printf(" ");

printf("%s\n", patt);

return;

}

}

if(s < text_length - patt_length)

t = (c * (t - text[s]* h) + text[s + patt_length])%q;

}

printf("Not match!\n");

}

int main(int argc, char * argv[])

{

char * text = NULL;

char * pattern = NULL;

if(argc != 3)

usage(argv[0]);

else

{

text = argv[1];

pattern = argv[2];

}

printf("text: %s\n", text);

printf("patn: %s\n", pattern);

rk_sm(pattern, text, strlen(pattern), strlen(text), 26, 13);

return 1;

}