Cod sursa(job #970242)

Utilizator Theorytheo .c Theory Data 6 iulie 2013 12:26:40
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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


const int Nmax = 2000009;
const int P = 73;
const int Mod1 = 100007;
const int Mod2 = 100021;

int N; int M; char A[Nmax]; char B[Nmax]; int q = 0; int Count; int P1 = 1, P2 = 1;

vector <int> V;

void Read() {

    fin >> A + 1; fin.get();
    fin >> B + 1;
    N = strlen(A + 1);
    M = strlen(B + 1);
}

void Solve() {

    int HashA1 = 0; int HashA2 = 0;  int Hash1 = 0; int Hash2 = 0;

    for(int i = 1; i <= N; ++i) {

        HashA1 = (P * HashA1 + A[i]) % Mod1;
        HashA2 = (P * HashA2 + A[i]) % Mod2;

        if(i > 1)
            P1 = (P * P1) % Mod1,
            P2 = (P * P2) % Mod2;
    }

    for(int i = 1; i <= N; ++i) {
        Hash1 = (P * Hash1 + B[i]) % Mod1;
        Hash2 = (P * Hash2 + B[i]) % Mod2;
    }

    if(Hash1 == HashA1 && Hash2 == HashA2)
        Count++, V.push_back(1);

    if(N >= M) return ;

    for(int i = N + 1; i <= M; ++i) {

        Hash1 = ((Hash1 - (P1 * B[i - N]) % Mod1 + Mod1)* P + B[i]) % Mod1;

        Hash2 = ((Hash2 - (P2 * B[i - N]) % Mod2 + Mod2)* P + B[i]) % Mod2;

        if(Hash1 == HashA1 && Hash2 == HashA2){
            ++Count;
            if(Count <= 1000)   V.push_back(i - N);
        }

    }

}

void Print() {

    fout << Count <<'\n';

    for(int i = 0 ; i < V.size(); ++i)
        fout << V[i] << " ";
}

int main() {

    Read();

    Solve (); Print ();

    return 0;
}