Cod sursa(job #1976883)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 4 mai 2017 14:44:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 2000002

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

char A[NMAX], B[NMAX];
unsigned long long Bpow[NMAX];

const int BASE = 29;

unsigned long long hashUp(const int N) {

    unsigned long long h = 0;

    Bpow[0] = 1;
    for (int i = 0; i < N; ++i) {

        Bpow[i + 1] = Bpow[i] * BASE;
        h = h * BASE + A[i];
    }
    return h;
}

int main() {

    fin >> A >> B;

    int N = strlen(A);
    int M = strlen(B);

    unsigned long long hashA = hashUp(N);

    int nrMatches = 0;
    vector<int> poz;

    unsigned long long hashB = 0;
    for (int i = 0; i < M; ++i) {

        hashB = hashB * BASE + B[i];

        if (i >= N)
            hashB -= Bpow[N] * B[i - N];

        if (i >= N - 1 && hashB == hashA) {

            nrMatches++;

            if (nrMatches <= 1000)
                poz.push_back(i - N + 1);
        }
    }

    fout << nrMatches << "\n";
    for (auto val: poz)
        fout << val << " ";

    return 0;
}