Cod sursa(job #943129)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 24 aprilie 2013 14:53:56
Problema Potrivirea sirurilor Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int P = 13;
const int MOD1 = 666013;
const int MOD2 = 666777;

char A[2000010], B[2000010];
int Sol[1010];

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

    in >> A >> B;
    N = strlen (A);
    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 ++){
        hashB1 = (hashB1 * P + B[i]) % MOD1;
        hashB2 = (hashB2 * P + B[i]) % MOD2;
    }

    if (hashA1 == hashB1 && hashA2 == hashB2)
        Sol[++ Sol[0]] = 1, Ans = 1;

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

        if (hashA1 == hashB1 && hashA2 == hashB2){
            Ans ++;
            if (Sol[0] < 1000)
                Sol[++ Sol[0]] = i - N + 1;
        }
    }

    out << Ans << "\n";
    for (i = 1; i <= Sol[0]; i ++)
        out << Sol[i] << " ";

    return 0;
}