Cod sursa(job #1166646)

Utilizator muresan_bogdanMuresan Bogdan muresan_bogdan Data 3 aprilie 2014 18:49:44
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<iostream>
#include<fstream>
#include<cstring>
#include<queue>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int KEY = 73;
const int MOD1 = 20233;
const int MOD2 = 20323;

int n, l, L, i, p1, p2, hashA1, hashA2, hashB1, hashB2, k;
string sent, word;
queue<int> sol;

int main() {
    getline(fin, word);
    getline(fin, sent);
    l = word.length();
    L = sent.length();
    p1 = 1;
    p2 = 1;
    for(i = 0; i < l; i++) {
        hashA1 = (((hashA1 * KEY) % MOD1) + word[i]) % MOD1;
        hashA2 = (((hashA2 * KEY) % MOD2) + word[i]) % MOD2;
        if(i != 0) {
            p1 = (p1 * KEY) % MOD1;
            p2 = (p2 * KEY) % MOD2;
        }
    }
    for(i = 0; i < l; i++) {
        hashB1 = (((hashB1 * KEY) % MOD1) + sent[i]) % MOD1;
        hashB2 = (((hashB2 * KEY) % MOD2) + sent[i]) % MOD2;
    }
    if((hashA1 == hashB1) && (hashA2 == hashB2)) {
        sol.push(0);
    }
    for(i = l; i < L; i++) {
        hashB1 = ((((hashB1 - ((sent[i-l] * p1) % MOD1) + MOD1) % MOD1) * KEY) % MOD1 + sent[i]) % MOD1;
        hashB2 = ((((hashB2 - ((sent[i-l] * p2) % MOD2) + MOD2) % MOD2) * KEY) % MOD2 + sent[i]) % MOD2;
        if((hashA1 == hashB1) && (hashA2 == hashB2)) {
            sol.push(i-l+1);
        }
    }
    k = 0;
    fout << sol.size() << '\n';
    while(!sol.empty() && (k <  1000)) {
        fout << sol.front() << ' ';
        sol.pop();
        k++;
    }
    fin.close();
    fout.close();
    return 0;
}