Cod sursa(job #3005184)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 16 martie 2023 20:03:44
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int BASE  = 26;
const int HASH1 = 1999997;
const int HASH2 = 1999993;
const int DIM   = 2000010;

char a[DIM], b[DIM];
bool match[DIM];

int main() {
    fin >> a >> b;
    int lenA = strlen(a);
    int lenB = strlen(b);

    if (lenA > lenB) {
        fout << 0;
        return 0;
    }

    int p1 = 1, p2 = 1;
    int hashA1 = 0, hashA2 = 0;
    int hashB1 = 0, hashB2 = 0;
    for (int i = 0; i < lenA; i++) {
        hashA1 = (hashA1 * BASE + a[i]) % HASH1;
        hashA2 = (hashA2 * BASE + a[i]) % HASH2;
        hashB1 = (hashB1 * BASE + b[i]) % HASH1;
        hashB2 = (hashB2 * BASE + b[i]) % HASH2;

        if (i != 0) {
            p1 = (p1 * BASE) % HASH1;
            p2 = (p2 * BASE) % HASH2;
        }
    }

    int matchCnt = 0;
    if (hashA1 == hashB1 && hashA2 == hashB2) {
        match[0] = true;
        matchCnt++;
    }
    for (int i = lenA; i < lenB; i++) {
        hashB1 = (((hashB1 - (p1 * b[i - lenA]) % HASH1) % HASH1) * BASE + b[i]) % HASH1;
        hashB2 = (((hashB2 - (p2 * b[i - lenA]) % HASH2) % HASH2) * BASE + b[i]) % HASH2;
        if (hashA1 == hashB1 && hashA2 == hashB2) {
            match[i - lenA + 1] = true;
            matchCnt++;
        }
    }

    fout << matchCnt << '\n';
    matchCnt = 0;
    for (int i = 0; i < lenB && matchCnt < 1000; i++) {
        if (match[i]) {
            fout << i << ' ';
            matchCnt++;
        }
    }

    return 0;
}