Cod sursa(job #806988)

Utilizator danalex97Dan H Alexandru danalex97 Data 3 noiembrie 2012 20:10:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int Nmax = 2000010;
const int M1 = 1000003;
const int M2 = 1000033;
const int Baza = 73;

char A[Nmax];int N;
char B[Nmax];int M;

int P1,P2;
int H1,H2;
int Act1,Act2,Co;
vector<int> V;

void Count( int i )
{
    if ( Act1 == H1 && Act2 == H2 )
    {
        ++Co;
        if ( V.size() < 1000 )
            V.push_back( i );
    }
}

int main()
{
    F.getline(A,Nmax,'\n');N=strlen(A);
    F.getline(B,Nmax,'\n');M=strlen(B);

    P1 = P2 = 1;
    for (int i=0;i<N;++i)
    {
        H1 = ( H1*Baza + A[i] ) % M1;
        H2 = ( H2*Baza + A[i] ) % M2;
        Act1 = ( Act1*Baza + B[i] ) % M1;
        Act2 = ( Act2*Baza + B[i] ) % M2;
    }
    for (int i=1;i<N;++i)
    {
        P1 = ( P1 * Baza ) % M1;
        P2 = ( P2 * Baza ) % M2;
    }

    Count( 0 );
    for (int i=N;i<M;++i)
    {
        Act1 = ((Act1 - (B[i-N] * P1) % M1 + M1) * Baza + B[i]) % M1;
        Act2 = ((Act2 - (B[i-N] * P2) % M2 + M2) * Baza + B[i]) % M2;
        Count( i-N+1 );
    }

    G<<Co<<'\n';
    for (int i=0;i<int(V.size());++i)
        G<<V[i]<<' ';
    G<<'\n';
}