Cod sursa(job #1951796)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 3 aprilie 2017 19:59:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 2e6 + 5;
const int firstMOD = 666013;
const int secondMOD = 10007;

bitset < NMax > good;

int main() {
    ios::sync_with_stdio(false);

    string a, b;
    fin >> a >> b;

    int n = (int)a.size();
    int m = (int)b.size();
    if(n > m) {
        fout << 0;
        return 0;
    }

    int firstPatHash, secondPatHash, firstRatio, secondRatio;
    firstPatHash = secondPatHash = 0;
    firstRatio = secondRatio = 1;
    for(int i = 0; i < n; i++) {
        firstPatHash = (firstPatHash * 2 + a[i]) % firstMOD;
        secondPatHash = (secondPatHash * 3 + a[i]) % secondMOD;

        if(i != 0) {
            firstRatio = (firstRatio * 2) % firstMOD;
            secondRatio = (secondRatio * 3) % secondMOD;
        }
    }

    int firstTextHash, secondTextHash;
    firstTextHash = secondTextHash = 0;

    for(int i = 0; i < n; i++) {
        firstTextHash = (firstTextHash * 2 + b[i]) % firstMOD;
        secondTextHash = (secondTextHash * 3 + b[i]) % secondMOD;
    }

    int ans = 0;
    if(firstTextHash == firstPatHash && secondTextHash == secondPatHash) {
        good[0] = true;
        ans++;
    }

    for(int i = n; i < m; i++) {
        firstTextHash = ((firstTextHash - (b[i - n] * firstRatio) % firstMOD + firstMOD) * 2 + b[i]) % firstMOD;
        secondTextHash = ((secondTextHash - (b[i - n] * secondRatio) % secondMOD + secondMOD) * 3 + b[i]) % secondMOD;

        if(firstTextHash == firstPatHash && secondTextHash == secondPatHash) {
            good[i - n + 1] = true;
            ans++;
        }
    }
    fout << ans << "\n";

    ans = 0;
    for(int i = 0; i < m && ans <= 1000; i++) {
        if(good[i] == true) {
            ans++;
            fout << i << " ";
        }
    }
    return 0;
}