Cod sursa(job #1292716)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 14 decembrie 2014 17:55:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int MAXN = 2000001;
const int P = 73;
const int MOD1 = 666013;
const int MOD2 = 666773;

char A[MAXN], B[MAXN];
bool Match[MAXN];

int main()
{
    int N, M, i;
    int hashA1 = 0, hashA2 = 0;
    int hash1 = 0, hash2 = 0;
    int P1 = 1, P2 = 1;
    int Ans = 0;

    in >> A;
    N = strlen (A);
    in >> B;
    M = strlen (B);

    if (N > M){
        out << "0";
        return 0;
    }

    for (i = 0; i < N; i ++){
        hashA1 = (hashA1 * P + A[i]) % MOD1;
        hashA2 = (hashA2 * P + A[i]) % MOD2;

        if (i){
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }
    }

    for (i = 0; i < N; i ++){
        hash1 = (hash1 * P + B[i]) % MOD1;
        hash2 = (hash2 * P + B[i]) % MOD2;
    }

    if (hash1 == hashA1 && hash2 == hashA2){
        Match[0] = 1;
        Ans ++;
    }

    for (i = N; i < M; i ++){
        hash1 = (((hash1 - (B[i - N] * P1)) % MOD1 + MOD1) * P + B[i]) % MOD1;
        hash2 = (((hash2 - (B[i - N] * P2)) % MOD2 + MOD2) * P + B[i]) % MOD2;

        if (hash1 == hashA1 && hash2 == hashA2){
            Ans ++;
            Match[i - N + 1] = 1;
        }
    }

    out << Ans << "\n";
    Ans = 0;
    for (i = 0; i < M && Ans < 1000; i ++)
        if (Match[i]){
            out << i << " ";
            Ans ++;
        }

    return 0;
}