Cod sursa(job #2154456)

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

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

const int MAXN = 2000005;
const int MOD1 = 666013;
const int MOD2 = 1e9 + 7;
const int Q = 3;
int n, m;
long long ha, ha2, hb, hb2, P1, P2;
char A[MAXN], B[MAXN];
vector<int> sol;

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;
    for (int i = 1; i < m; ++i) {
        P1 = (P1 * Q) % MOD1;
        P2 = (P2 * Q) % MOD2;
    }

    // calculeaza hash-ul lui A si B[0..m-1]
    for (int i = 0; i < m; ++i) {
        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.push_back(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.push_back(i);
            if (sol.size() == 1000) break;
        }
    }

    out << sol.size() << "\n";
    for (int i : sol) out << i << " ";

    return 0;
}