// Rabin-Karp algorithm implementation
#include <string.h>
#include <iostream>
using namespace std;
#define d 10

int rabinKarp(char pattern[100], char text[100], int q)
{
  int m = strlen(pattern);
  int n = strlen(text);
  int i, j;
  int p = 0;
  int t = 0;
  int h = 1;
  int count = -1;

  for (i = 0; i < m - 1; i++)
    h = (h * d) % q;
  //cout  << "\n h value is " << h << endl;

  // Calculate hash value for pattern and text
  for (i = 0; i < m; i++)
  {
    p = (d * p + pattern[i]) % q;
    t = (d * t + text[i]) % q;
  }

  // Find the match
  for (i = 0; i <= n - m; i++)
    {

        if (p == t)
        {
            for (j = 0; j < m; j++)
            {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == m)
            {
                cout << "Pattern is found at position: " << i + 1 << endl;
                count++;
            }
        }

        if (i < n - m)
        {
            t = (d * (t - text[i] * h) + text[i + m]) % q;

            if (t < 0)
                t = (t + q);
        }
    }
    return count;
}

int main()
{
  char text[100], pattern[100];

  cout << "\nEnter the main String : ";
  gets(text);

  cout << "\nEnter the Pattern/Search String : ";
  gets(pattern);

  int q = 13;

  int res = rabinKarp(pattern, text, q);
  if(res < 0)
    cout << "Pattern not found in the text" << endl;
}