C++ Program to Implement Rolling Hash

This C++ Program demonstrates operations on Rolling Hash

Here is source code of the C++ Program to demonstrate Rolling Hash. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Implement Rolling Hash

```
 */
```
```
#include <iostream>
```
```
#include <string>
```
```
using namespace std;
```
```
 
```
```
const unsigned PRIME_BASE = 257;
```
```
const unsigned PRIME_MOD = 1000000007;
```
```
 
```
```
/*
```
```
 * Hash Function
```
```
 */
```
```
unsigned hash(const string& s)
```
```
{
```
```
    long long ret = 0;
```
```
    for (int i = 0; i < s.size(); i++)
```
```
    {
```
```
        ret = ret * PRIME_BASE + s[i];
```
```
        ret %= PRIME_MOD;
```
```
    }
```
```
    return ret;
```
```
}
```
```
 
```
```
/*
```

 * Rabin-Karp (Rolling Hash Implementation)

```
 */
```

int rabin_karp(const string& needle, const string& haystack)

```
{
```
```
    long long hash1 = hash(needle);
```
```
    long long hash2 = 0;
```
```
    long long power = 1;
```

    for (int i = 0; i < needle.size(); i++)

        power = (power * PRIME_BASE) % PRIME_MOD;

```
 
```

    for (int i = 0; i < haystack.size(); i++)

```
    {
```

        hash2 = hash2*PRIME_BASE + haystack[i];

```
        hash2 %= PRIME_MOD;
```
```
 
```
```
    	if (i >= needle.size())
```
```
    	{
```

            hash2 -= power * haystack[i-needle.size()] % PRIME_MOD;

```
            if (hash2 < 0)
```
```
                hash2 += PRIME_MOD;
```
```
        }
```

    	if (i >= needle.size()-1 && hash1 == hash2)

            return i - (needle.size()-1);

```
    }
```
```
 
```
```
    return -1;
```
```
}
```
```
 
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```

    cout<<"---------------------------"<<endl;

    cout<<"Rolling Hash Implementation"<<endl;

    cout<<"---------------------------"<<endl;

```
    string s1,s2;
```
```
    cout<<"Enter Original String: ";
```
```
    getline(cin,s1);
```
```
    cout<<"Enter String to find: ";
```
```
    cin>>s2;
```
```
    if(rabin_karp(s2, s1) == -1)
```
```
        cout<<"String not found"<<endl;
```
```
    else
```

        cout<<"String "<<s2<<"found at position "<<rabin_karp(s2, s1)<<endl;

```
        return 0;
```
```
}
```

$ g++ rolling.cpp
$ a.out
---------------------------
Rolling Hash Implementation
---------------------------
Enter Original String: sanfoundry
Enter String to find: o
String ofound at position 4
 
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - Subtract Two Numbers Represented as Linked Lists in C++

» Next - C++ Program to Implement Bloom Filter

Related Posts:

Recommended Articles: