twKPaB - Online C++ Compiler & Debugging Tool

#include<bits/stdc++.h>

using namespace std;

#define len 7
int base=10;
int power[len];

void init()
{
    power[0]=1;
    for(int i=1;i<len;i++)
    {
        power[i]=power[i-1]*base;
    }
}

int get_index(char ch)
{
    return ch-'0';
}

void prefixHash(string s,vector<int> &ph)
{
    int n=ph.size();
    ph[0]=get_index(s[0]);
    for(int i=1;i<n;i++)
    {
        ph[i]=ph[i-1]*base+get_index(s[i]);
    }
}

int calcHash(int l,int r,vector<int> &ph)
{
    if(l==0) return ph[r];
    return ph[r]-(ph[l-1]*power[r-l+1]);
}

int main()
{
    init();
    //string s="123456";
    string txt="1211212133333333333";
    string pat="121";
    int n=txt.size(),m=pat.size();

    vector<int> ph1(n),ph2(m);
    prefixHash(txt,ph1);
    prefixHash(pat,ph2);


    for(int i=0;i+m<=n;i++) /// i=3
    {
        int x=calcHash(i,i+m-1,ph1);
        int y=calcHash(0,2,ph2);
        if(x==y)
        {
            cout << "Found " << pat << " at i=" << i << endl;
        }
    }
    //for(int i=0;i<n;i++) cout << ph[i] << endl;
    //cout << calcHash(2,4,ph);


    return 0;
}

/**
12112121
**/