الگوریتم رابین کارپ (Rabin-Karp Algorithm) — به زبان ساده

1/* Following program is a C++ implementation of Rabin Karp  
2Algorithm given in the CLRS book */
3#include <bits/stdc++.h> 
4using namespace std; 
5  
6// d is the number of characters in the input alphabet  
7#define d 256  
8  
9/* pat -> pattern  
10    txt -> text  
11    q -> A prime number  
12*/
13void search(char pat[], char txt[], int q)  
14{  
15    int M = strlen(pat);  
16    int N = strlen(txt);  
17    int i, j;  
18    int p = 0; // hash value for pattern  
19    int t = 0; // hash value for txt  
20    int h = 1;  
21  
22    // The value of h would be "pow(d, M-1)%q"  
23    for (i = 0; i < M - 1; i++)  
24        h = (h * d) % q;  
25  
26    // Calculate the hash value of pattern and first  
27    // window of text  
28    for (i = 0; i < M; i++)  
29    {  
30        p = (d * p + pat[i]) % q;  
31        t = (d * t + txt[i]) % q;  
32    }  
33  
34    // Slide the pattern over text one by one  
35    for (i = 0; i <= N - M; i++)  
36    {  
37  
38        // Check the hash values of current window of text  
39        // and pattern. If the hash values match then only  
40        // check for characters on by one  
41        if ( p == t )  
42        {  
43            /* Check for characters one by one */
44            for (j = 0; j < M; j++)  
45            {  
46                if (txt[i+j] != pat[j])  
47                    break;  
48            }  
49  
50            // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]  
51            if (j == M)  
52                cout<<"Pattern found at index "<< i<<endl;  
53        }  
54  
55        // Calculate hash value for next window of text: Remove  
56        // leading digit, add trailing digit  
57        if ( i < N-M )  
58        {  
59            t = (d*(t - txt[i]*h) + txt[i+M])%q;  
60  
61            // We might get negative value of t, converting it  
62            // to positive  
63            if (t < 0)  
64            t = (t + q);  
65        }  
66    }  
67}  
68  
69/* Driver code */
70int main()  
71{  
72    char txt[] = "GEEKS FOR GEEKS";  
73    char pat[] = "GEEK";  
74    int q = 101; // A prime number  
75    search(pat, txt, q);  
76    return 0;  
77}  
78  
79// This is code is contributed by rathbhupendra 

1/* Following program is a C implementation of Rabin Karp 
2Algorithm given in the CLRS book */
3#include<stdio.h> 
4#include<string.h> 
5  
6// d is the number of characters in the input alphabet 
7#define d 256 
8  
9/* pat -> pattern 
10    txt -> text 
11    q -> A prime number 
12*/
13void search(char pat[], char txt[], int q) 
14{ 
15    int M = strlen(pat); 
16    int N = strlen(txt); 
17    int i, j; 
18    int p = 0; // hash value for pattern 
19    int t = 0; // hash value for txt 
20    int h = 1; 
21  
22    // The value of h would be "pow(d, M-1)%q" 
23    for (i = 0; i < M-1; i++) 
24        h = (h*d)%q; 
25  
26    // Calculate the hash value of pattern and first 
27    // window of text 
28    for (i = 0; i < M; i++) 
29    { 
30        p = (d*p + pat[i])%q; 
31        t = (d*t + txt[i])%q; 
32    } 
33  
34    // Slide the pattern over text one by one 
35    for (i = 0; i <= N - M; i++) 
36    { 
37  
38        // Check the hash values of current window of text 
39        // and pattern. If the hash values match then only 
40        // check for characters on by one 
41        if ( p == t ) 
42        { 
43            /* Check for characters one by one */
44            for (j = 0; j < M; j++) 
45            { 
46                if (txt[i+j] != pat[j]) 
47                    break; 
48            } 
49  
50            // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1] 
51            if (j == M) 
52                printf("Pattern found at index %d \n", i); 
53        } 
54  
55        // Calculate hash value for next window of text: Remove 
56        // leading digit, add trailing digit 
57        if ( i < N-M ) 
58        { 
59            t = (d*(t - txt[i]*h) + txt[i+M])%q; 
60  
61            // We might get negative value of t, converting it 
62            // to positive 
63            if (t < 0) 
64            t = (t + q); 
65        } 
66    } 
67} 
68  
69/* Driver program to test above function */
70int main() 
71{ 
72    char txt[] = "GEEKS FOR GEEKS"; 
73    char pat[] = "GEEK"; 
74    int q = 101; // A prime number 
75    search(pat, txt, q); 
76    return 0; 
77}

1// Following program is a Java implementation  
2// of Rabin Karp Algorithm given in the CLRS book 
3  
4public class Main  
5{ 
6    // d is the number of characters in the input alphabet 
7    public final static int d = 256; 
8      
9    /* pat -> pattern 
10        txt -> text 
11        q -> A prime number 
12    */
13    static void search(String pat, String txt, int q) 
14    { 
15        int M = pat.length(); 
16        int N = txt.length(); 
17        int i, j; 
18        int p = 0; // hash value for pattern 
19        int t = 0; // hash value for txt 
20        int h = 1; 
21      
22        // The value of h would be "pow(d, M-1)%q" 
23        for (i = 0; i < M-1; i++) 
24            h = (h*d)%q; 
25      
26        // Calculate the hash value of pattern and first 
27        // window of text 
28        for (i = 0; i < M; i++) 
29        { 
30            p = (d*p + pat.charAt(i))%q; 
31            t = (d*t + txt.charAt(i))%q; 
32        } 
33      
34        // Slide the pattern over text one by one 
35        for (i = 0; i <= N - M; i++) 
36        { 
37      
38            // Check the hash values of current window of text 
39            // and pattern. If the hash values match then only 
40            // check for characters on by one 
41            if ( p == t ) 
42            { 
43                /* Check for characters one by one */
44                for (j = 0; j < M; j++) 
45                { 
46                    if (txt.charAt(i+j) != pat.charAt(j)) 
47                        break; 
48                } 
49      
50                // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1] 
51                if (j == M) 
52                    System.out.println("Pattern found at index " + i); 
53            } 
54      
55            // Calculate hash value for next window of text: Remove 
56            // leading digit, add trailing digit 
57            if ( i < N-M ) 
58            { 
59                t = (d*(t - txt.charAt(i)*h) + txt.charAt(i+M))%q; 
60      
61                // We might get negative value of t, converting it 
62                // to positive 
63                if (t < 0) 
64                t = (t + q); 
65            } 
66        } 
67    } 
68      
69    /* Driver program to test above function */
70    public static void main(String[] args) 
71    { 
72        String txt = "GEEKS FOR GEEKS"; 
73        String pat = "GEEK"; 
74        int q = 101; // A prime number 
75        search(pat, txt, q); 
76    } 
77} 
78  
79// This code is contributed by nuclode 

1# Following program is the python implementation of 
2# Rabin Karp Algorithm given in CLRS book 
3  
4# d is the number of characters in the input alphabet 
5d = 256
6  
7# pat  -> pattern 
8# txt  -> text 
9# q    -> A prime number 
10  
11def search(pat, txt, q): 
12    M = len(pat) 
13    N = len(txt) 
14    i = 0
15    j = 0
16    p = 0    # hash value for pattern 
17    t = 0    # hash value for txt 
18    h = 1
19  
20    # The value of h would be "pow(d, M-1)%q" 
21    for i in xrange(M-1): 
22        h = (h*d)%q 
23  
24    # Calculate the hash value of pattern and first window 
25    # of text 
26    for i in xrange(M): 
27        p = (d*p + ord(pat[i]))%q 
28        t = (d*t + ord(txt[i]))%q 
29  
30    # Slide the pattern over text one by one 
31    for i in xrange(N-M+1): 
32        # Check the hash values of current window of text and 
33        # pattern if the hash values match then only check 
34        # for characters on by one 
35        if p==t: 
36            # Check for characters one by one 
37            for j in xrange(M): 
38                if txt[i+j] != pat[j]: 
39                    break
40  
41            j+=1
42            # if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1] 
43            if j==M: 
44                print "Pattern found at index " + str(i) 
45  
46        # Calculate hash value for next window of text: Remove 
47        # leading digit, add trailing digit 
48        if i < N-M: 
49            t = (d*(t-ord(txt[i])*h) + ord(txt[i+M]))%q 
50  
51            # We might get negative values of t, converting it to 
52            # positive 
53            if t < 0: 
54                t = t+q 
55  
56# Driver program to test the above function 
57txt = "GEEKS FOR GEEKS"
58pat = "GEEK"
59q = 101 # A prime number 
60search(pat,txt,q) 
61  
62# This code is contributed by Bhavya Jain

1// Following program is a C# implementation  
2// of Rabin Karp Algorithm given in the CLRS book  
3using System; 
4public class GFG  
5{  
6    // d is the number of characters in the input alphabet  
7    public readonly static int d = 256;  
8      
9    /* pat -> pattern  
10        txt -> text  
11        q -> A prime number  
12    */
13    static void search(String pat, String txt, int q)  
14    {  
15        int M = pat.Length;  
16        int N = txt.Length;  
17        int i, j;  
18        int p = 0; // hash value for pattern  
19        int t = 0; // hash value for txt  
20        int h = 1;  
21      
22        // The value of h would be "pow(d, M-1)%q"  
23        for (i = 0; i < M-1; i++)  
24            h = (h*d)%q;  
25      
26        // Calculate the hash value of pattern and first  
27        // window of text  
28        for (i = 0; i < M; i++)  
29        {  
30            p = (d*p + pat[i])%q;  
31            t = (d*t + txt[i])%q;  
32        }  
33      
34        // Slide the pattern over text one by one  
35        for (i = 0; i <= N - M; i++)  
36        {  
37      
38            // Check the hash values of current window of text  
39            // and pattern. If the hash values match then only  
40            // check for characters on by one  
41            if ( p == t )  
42            {  
43                /* Check for characters one by one */
44                for (j = 0; j < M; j++)  
45                {  
46                    if (txt[i+j] != pat[j])  
47                        break;  
48                }  
49      
50                // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]  
51                if (j == M)  
52                    Console.WriteLine("Pattern found at index " + i);  
53            }  
54      
55            // Calculate hash value for next window of text: Remove  
56            // leading digit, add trailing digit  
57            if ( i < N-M )  
58            {  
59                t = (d*(t - txt[i]*h) + txt[i+M])%q;  
60      
61                // We might get negative value of t, converting it  
62                // to positive  
63                if (t < 0)  
64                t = (t + q);  
65            }  
66        }  
67    }  
68      
69    /* Driver program to test above function */
70    public static void Main()  
71    {  
72        String txt = "GEEKS FOR GEEKS";  
73        String pat = "GEEK";  
74        int q = 101; // A prime number  
75        search(pat, txt, q);  
76    }  
77}  
78  
79// This code is contributed by PrinciRaj19992

1<?php 
2// Following program is a PHP  
3// implementation of Rabin Karp 
4// Algorithm given in the CLRS book  
5  
6// d is the number of characters 
7// in the input alphabet 
8$d = 256; 
9  
10/* pat -> pattern 
11   txt -> text 
12   q -> A prime number 
13*/
14function search($pat, $txt, $q) 
15{ 
16    $M = strlen($pat); 
17    $N = strlen($txt); 
18    $i; $j; 
19    $p = 0; // hash value  
20            // for pattern 
21    $t = 0; // hash value  
22            // for txt 
23    $h = 1; 
24    $d =1; 
25  
26    // The value of h would 
27    // be "pow(d, M-1)%q" 
28    for ($i = 0; $i < $M - 1; $i++) 
29        $h = ($h * $d) % $q; 
30  
31    // Calculate the hash value 
32    // of pattern and first 
33    // window of text 
34    for ($i = 0; $i < $M; $i++) 
35    { 
36        $p = ($d * $p + $pat[$i]) % $q; 
37        $t = ($d * $t + $txt[$i]) % $q; 
38    } 
39  
40    // Slide the pattern over 
41    // text one by one 
42    for ($i = 0; $i <= $N - $M; $i++) 
43    { 
44  
45        // Check the hash values of  
46        // current window of text 
47        // and pattern. If the hash 
48        // values match then only 
49        // check for characters on 
50        // by one 
51        if ($p == $t) 
52        { 
53            // Check for characters 
54            // one by one 
55            for ($j = 0; $j < $M; $j++) 
56            { 
57                if ($txt[$i + $j] != $pat[$j]) 
58                    break; 
59            } 
60  
61            // if p == t and pat[0...M-1] =  
62            // txt[i, i+1, ...i+M-1] 
63            if ($j == $M) 
64                echo "Pattern found at index ", 
65                                      $i, "\n"; 
66        } 
67  
68        // Calculate hash value for  
69        // next window of text:  
70        // Remove leading digit, 
71        // add trailing digit 
72        if ($i < $N - $M) 
73        { 
74            $t = ($d * ($t - $txt[$i] *  
75                        $h) + $txt[$i +  
76                             $M]) % $q; 
77  
78            // We might get negative  
79            // value of t, converting 
80            // it to positive 
81            if ($t < 0) 
82            $t = ($t + $q); 
83        } 
84    } 
85} 
86  
87// Driver Code 
88$txt = "GEEKS FOR GEEKS"; 
89$pat = "GEEK"; 
90$q = 101; // A prime number 
91search($pat, $txt, $q); 
92  
93// This code is contributed 
94// by ajit 
95?>