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);
}

 

/*Algorithm~*/

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;
}