Cod sursa(job #1106238)

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

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

const int MOD = 10007;
const int KEY = 29;
const int MAXN = 20000002;

string word, sentence;
int last, lung, i, hashA, hashB, k, pmax;
bool sol[MAXN];

int main() {
    fin >> word;
    fin >> sentence;
    lung = word.length();
    last = sentence.length();
    hashA = 0;
    pmax = 1;
    for(i = 0; i < lung; i++) {
        hashA = (hashA * KEY + word[i]) % MOD;
        if(i != 0)
            pmax = (pmax * KEY) % MOD;
    }
    for(i = 0; i < lung; i++) {
        hashB = (hashB * KEY + sentence[i]) % MOD;
    }
    k = 0;
    if(hashA == hashB) {
        sol[0] = 1;
        k++;
    }
    for(i = lung; i < last; i++) {
        hashB = ((hashB - (sentence[i - lung] * pmax) % MOD) * KEY + sentence[i]) % MOD;
        if(hashB == hashA) {
            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;
}