data-structure-and-algorithm/rabin_karp.cpp at master · ywen-cmd/data-structure-and-algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>

using namespace std;

/**********************************************
    rabin_karp
**********************************************/
#define RADIX   (256)
#define PRIME   (101)

void print_matching_result(const char *pval, int s)
{
    for(int i = 0; i < s; i++)
        printf(" ");
    printf("%s\n",pval);
}

void rabin_karp(const char *t, const char *p)
{
    printf("**********************************************\n");
    printf("%s\n",t);

    int nt = strlen(t), np = strlen(p);
    int pval = 0, tval = 0, h = 1;

    for(int i = 0; i < np-1; i++)
        h = (h*RADIX)%PRIME;

    for(int i = 0; i < np; i++)
    {
        pval = (RADIX*pval+p[i]) % PRIME;
        tval = (RADIX*tval+t[i]) % PRIME;
    }

    for(int i = 0; i <= nt-np; i++)
    {
        if(pval == tval)
        {
            int j;
            for(j = 0; j < np; j++)
                if(t[i+j] != p[j])
                    break;
            if(j == np)
                print_matching_result(p, i);
        }

        if(i == nt-np)
            return;

        tval = ((tval-t[i]*h)*RADIX + t[i+np])%PRIME;
        if(tval < 0)
            tval = tval + PRIME;
    }
}

int main()
{
    rabin_karp("ABABABABC", "ABAB");
    rabin_karp("ABABCABAB", "ABAB");
    rabin_karp("AAAAAAA", "AAA");
    rabin_karp("ABABABC", "ABABC");
    rabin_karp("XYXZdeOXZZKWXYZ", "WXYZ");
    rabin_karp("GCAATGCCTATGTGACCTATGTG", "TATGTG");
    rabin_karp("AGATACGATATATAC", "ATATA");
    rabin_karp("CATCGCGGAGAGTATAGCAGAGAG", "GCAGAGAG");
    return 0;
}