Cod sursa(job #922501)

Utilizator danalex97Dan H Alexandru danalex97 Data 22 martie 2013 11:24:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

const int Nmax = 2000010;

typedef unsigned long long I64;
const int B1 = 73;
const int B2 = 79;

I64 V1,V2;int N;
I64 W1,W2;int M;

I64 P1 = 1LL;
I64 P2 = 1LL;

char A[Nmax],B[Nmax];

vector<int> V;int Co;

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

void Count(int i)
{
    ++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);

    for (int i=0;i<N;++i)
        V1 = ( V1 * B1 ) + A[i],
        V2 = ( V2 * B2 ) + A[i];
    for (int i=1;i<N;++i)
        P1 *= B1,
        P2 *= B2;

    for (int i=0;i<N;++i)
        W1 = ( W1 * B1 ) + B[i],
        W2 = ( W2 * B2 ) + B[i];
    if ( W1 == V1 && W2 == V2  ) Count(0);

    for (int i=N;i<M;++i)
    {
        W1 = ( W1 - ( B[i-N] * P1 ) ) * B1 + B[i];
        W2 = ( W2 - ( B[i-N] * P2 ) ) * B2 + B[i];
        if ( W1 == V1 && W2 == V2  ) Count(i-N+1);
    }

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