#include <iostream>

// Rabin-Karp on its own, but still using the bad decimal hash
// so the workings can be seen.

typedef unsigned int ui;

const ui mult = 100,
         modu = 1000000;

ui hash(string s)
{ ui h = 0;
  int n = s.length();
  for (int i=0; i<n; i+=1)
    h = (h * mult + s[i]) % modu;
  return h; }

int main()
{ string big, little;
  cout << "little string: ";
  cin >> little;
  int littlelen = little.length();
  ui hashlittle = hash(little);

  cout << "big string: ";
  cin >> big;
  int biglen = big.length();

  ui lastcharweight = 1;
  for (int i = 1; i < littlelen; i += 1)
    lastcharweight = (lastcharweight * mult) % modu;

  ui hashcurr = hash(big.substr(0, littlelen));

  for (int start = 0; start <= biglen-littlelen; start += 1)
  { cout << start << " to " << start+littlelen-1 << ": " << hashcurr << ", want " << hashlittle << "\n";
    if (hashcurr == hashlittle) cout << "match\n";

    hashcurr = (hashcurr + modu - (lastcharweight * big[start] % modu)) % modu;
    hashcurr = (hashcurr * mult + big[start+littlelen]) % modu; } }