Cod sursa(job #2482999)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 29 octombrie 2019 09:50:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int MOD1 = 2000003, MOD2 = 2000029, BASE = 256, MAXS = 2000010, MAXN = 1000;
char str[MAXS], sub[MAXS];
int pos[MAXN], k, n, m, subHash1, subHash2, hash1, hash2, power1 = 1, power2 = 1;

void read() {
    fin.getline(sub, MAXS);
    fin.getline(str, MAXS);
    n = strlen(str);
    m = strlen(sub);
}

void calculateHashes() {
    for (int i = 0; i < m; ++i) {
        subHash1 = (subHash1 * BASE + sub[i]) % MOD1;
        subHash2 = (subHash2 * BASE + sub[i]) % MOD2;
        hash1 = (hash1 * BASE + str[i]) % MOD1;
        hash2 = (hash2 * BASE + str[i]) % MOD2;
        if (i) {
            power1 = (power1 * BASE) % MOD1;
            power2 = (power2 * BASE) % MOD2;
        }
    }
}

void solve() {
    if (hash1 == subHash1 && hash2 == subHash2)
        pos[k++] = 0;
    for (int i = m; i < n; ++i) {
        hash1 = ((hash1 - (str[i - m] * power1) % MOD1 + MOD1) * BASE + str[i]) % MOD1;
        hash2 = ((hash2 - (str[i - m] * power2) % MOD2 + MOD2) * BASE + str[i]) % MOD2;
        if (hash1 == subHash1 && hash2 == subHash2) {
            if (k < 1000)
                pos[k] = i - m + 1;
            ++k;
        }
    }
}

void print() {
    fout << k << '\n';
    if (k > 1000)
        k = 1000;
    for (int i = 0; i < k; ++i)
        fout << pos[i] << ' ';
}

int main() {
    read();
    calculateHashes();
    solve();
    print();
    return 0;
}