Cod sursa(job #1437865)

Utilizator BLz0rDospra Cristian BLz0r Data 18 mai 2015 18:50:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define Nmax 2000002

FILE *f = fopen ( "strmatch.in", "r" );
FILE *g = fopen ( "strmatch.out", "w" );

char A[Nmax], B[Nmax];
int Pi[Nmax], N, M, nrMatch;
vector < int > sol;

void Prefix (){
    int k = 0;
    for ( int i = 2; i <= N; ++i ){
        while ( k > 0 && A[k+1] != A[i] )
            k = Pi[k];
        if ( A[k+1] == A[i] )
            k++;
        Pi[i] = k;
    }
}

void Match(){
    int k = 0;

    for ( int i = 1; i <= M; ++i ){
        while ( k > 0 && A[k+1] != B[i] )
            k = Pi[k];
        if ( A[k+1] == B[i] )
            k++;

        if ( k == N ){
            nrMatch++;
            if ( nrMatch <= 1000 )
                sol.push_back( i - N );
        }
    }

}

int main(){

    vector < int > :: iterator it;

    fscanf ( f, "%s%*c", A + 1 );
    fscanf ( f, "%s", B + 1 );

    N = strlen ( A + 1 );
    M = strlen ( B + 1 );

    if ( N > M ){
        fprintf ( g, "0" );
        return 0;
    }

    Prefix ();
    Match();

    fprintf ( g, "%d\n", nrMatch );

    for ( it = sol.begin(); it < sol.end(); ++it )
        fprintf ( g, "%d ", *it );

    return 0;
}