Cod sursa(job #1106286)

Utilizator muresan_bogdanMuresan Bogdan muresan_bogdan Data 12 februarie 2014 18:16:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

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

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

string word, sentence;
int last, lung, i, hashA1, hashA2, hashB1, hashB2, k, pmax1, pmax2;
bool sol[MAXN];

int main() {
    fin >> word;
    fin >> sentence;
    lung = word.length();
    last = sentence.length();
    hashA1 = hashA2 = 0;
    pmax1 = pmax2 = 1;
    for(i = 0; i < lung; i++) {
        hashA1 = (hashA1 * KEY + word[i]) % MOD1;
        hashA2 = (hashA2 * KEY + word[i]) % MOD2;
        if(i != 0) {
            pmax1 = (pmax1 * KEY) % MOD1;
            pmax2 = (pmax2 * KEY) % MOD2;
        }
    }
    hashB1 = hashB2 = 0;
    for(i = 0; i < lung; i++) {
        hashB1 = (hashB1 * KEY + sentence[i]) % MOD1;
        hashB2 = (hashB2 * KEY + sentence[i]) % MOD2;
    }
    k = 0;
    if((hashA1 == hashB1) && (hashA2 == hashB2)) {
        sol[0] = 1;
        k++;
    }
    for(i = lung; i < last; i++) {
        hashB1 = ((hashB1 - (sentence[i - lung] * pmax1) % MOD1 + MOD1) * KEY + sentence[i]) % MOD1;
        hashB2 = ((hashB2 - (sentence[i - lung] * pmax2) % MOD2 + MOD2) * KEY + sentence[i]) % MOD2;
        if((hashB1 == hashA1) && (hashB2 == hashA2)) {
            sol[i - lung + 1] = 1;
            k++;
        }
    }
    fout << k << '\n';
    k = 0;
    for(i = 0; i < MAXN && k < 1000; i++) {
        if(sol[i]) {
            fout << i << ' ';
            k++;
        }
    }
    fin.close();
    fout.close();
    return 0;
}