Cod sursa(job #1951802)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 3 aprilie 2017 20:02:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 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;
const int firstBase = 27;
const int secondBase = 28;

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 * firstBase + a[i]) % firstMOD;
        secondPatHash = (secondPatHash * secondBase + a[i]) % secondMOD;

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

    int firstTextHash, secondTextHash;
    firstTextHash = secondTextHash = 0;

    for(int i = 0; i < n; i++) {
        firstTextHash = (firstTextHash * firstBase + b[i]) % firstMOD;
        secondTextHash = (secondTextHash * secondBase + 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) * firstBase + b[i]) % firstMOD;
        secondTextHash = ((secondTextHash - (b[i - n] * secondRatio) % secondMOD + secondMOD) * secondBase + b[i]) % secondMOD;

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

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