17

Algorithm : Z Algorithm

void matchPattern(string text, string pattern) {
	string concate = pattern + "$" + text;
 	int lenText = text.length(), lenPat = pattern.length();
 	VI Z = getZarr(concate);
 	for (int i=0; i<concate.length(); i++) {
 		if (Z[i] == lenPat)
 			cout << "Pattern Found at " << (i-lenPat-1) << endl;
 	}
 }

Algorithm        : Robin Carp string matching, Double Hash
Compleixity      : O(n + m)

const ll B = 347;
const ll M = 1e9+7;

const ll Btemp = 313;
const ll Mtemp = 1e9+9;

PLL Hash(const string &s, int m) {      // double hash
    ll power = 1;
    ll powertemp = 1;

    ll h = 0;
    ll htemp = 0;

    for (int i=m-1; i>=0; i--) {
        h = h + (s[i]*power) % M;
        h = h % M;

        power = (power*B) % M;
        htemp = htemp + (s[i]*powertemp) % Mtemp;
        htemp = htemp % M;
        powertemp = (powertemp*Btemp) % Mtemp;
    }
    return mk(h, htemp);
}

ll match(const string &text, const string &pattern) {
    int n = text.size();
    int m = pattern.size();
    if (n < m)
        return -1;
    if (n==0 or m==0)
        return -1;
    PLL hash_t = Hash(text, m);
    PLL hash_p = Hash(pattern, m);

	ll hash_text = hash_t.first;
    ll hash_text_temp = hash_t.second;

	ll hash_pattern = hash_p.first;
    ll hash_pattern_temp = hash_p.second;

	if (hash_text==hash_pattern and hash_text_temp==hash_pattern_temp)
        return 0;
   	ll power = 1;
    ll powertemp = 1;
    for (int i=1; i<=m-1; i++) {
        power = (power*B) % M;
        powertemp = (powertemp*Btemp) % Mtemp;
    }
    for (int i=m; i<n; i++) {
        hash_text = (hash_text - (text[i-m]*power) % M) % M;
        hash_text = (hash_text + M) % M;
        hash_text = (hash_text * B) % M;
        hash_text = (hash_text + text[i]) % M;

        hash_text_temp = (hash_text_temp - (text[i-m]*powertemp) % Mtemp) % Mtemp;
        hash_text_temp = (hash_text_temp + Mtemp) % Mtemp;
        hash_text_temp = (hash_text_temp * Btemp) % Mtemp;
        hash_text_temp = (hash_text_temp + text[i]) % Mtemp;

        if (hash_text == hash_pattern and hash_text_temp == hash_pattern_temp) {
            return i-m+1;
        }
    }
    return -1;
}