Cod sursa(job #2154480)

Utilizator savigunFeleaga Dragos-George savigun Data 6 martie 2018 23:13:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

const int MAXN = 2000005;
const int MOD1 = 100007;
const int MOD2 = 100009;
const int Q = 127;
int n, m;
int ha, ha2, hb, hb2, P1, P2;
char A[MAXN], B[MAXN];
int sol[1005];

int main()
{
    in >> A >> B;
    n = strlen(B);
    m = strlen(A);
    if (m > n) {
        out << 0;
        return 0;
    }

    // calculeaza Q^(m-1)
    P1 = P2 = 1;

    // calculeaza hash-ul lui A si B[0..m-1]
    for (int i = 0; i < m; ++i) {
        if (i != 0) {
            P1 = (P1 * Q) % MOD1;
            P2 = (P2 * Q) % MOD2;
        }
        ha = (ha * Q + A[i]) % MOD1;
        ha2 = (ha2 * Q + A[i]) % MOD2;
        hb = (hb * Q + B[i]) % MOD1;
        hb2 = (hb2 * Q + B[i]) % MOD2;
    }

    if (ha == hb && ha2 == hb2) sol[++sol[0]] = 0;

    for (int i = 1; i <= n - m; ++i) {
        hb = ((hb - (B[i-1] * P1) % MOD1 + MOD1) * Q + B[i + m - 1]) % MOD1;
        hb2 = ((hb2 - (B[i-1] * P2) % MOD2 + MOD2) * Q + B[i + m - 1]) % MOD2;
        if (ha == hb && ha2 == hb2) {
            sol[0]++;
            if (sol[0] <= 1000) sol[sol[0]] = i;
        }
    }

    out << sol[0] << "\n";
    for (int i = 1; i <= min(sol[0], 1000); ++i) out << sol[i] << " ";

    return 0;
}