Cod sursa(job #1406948)

Utilizator MrWhiteDELETEME MrWhite Data 29 martie 2015 17:51:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define N_MAX                           2000001

char A[N_MAX], B[N_MAX];

typedef struct t_matches {
    int len, pos[N_MAX];
} t_matches;

t_matches m;

void KMP(char *a , char *S , t_matches *matches ){

    matches->len = 0;

    int LS = strlen( S );
    int La = strlen( a );

    char Str[ LS + La + 2 ];
    int P[ LS + La + 2 ]; memset(P, 0, sizeof(P));
    int fail = 0;

    strcpy( Str + 1 , a );
    Str[ La + 1 ] = '*';
    strcpy( Str + La + 2 , S );

    P[1] = 0;

    for( int i = 2 ; i <= LS + La + 1 ; i++ ){
        fail = P[i-1];

        while( Str[fail+1] != Str[i] && fail != 0 )
            fail = P[fail];

        if( Str[fail+1] == Str[i] )
            P[i] = fail + 1;
        if( P[i] == La ){
            matches->pos[ matches->len++ ] = i - 2 * La - 1;
        }

    }

}

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

    fin >> A >> B;
    KMP(A, B, &m);

    fout << m.len << "\n";
    for (int i = 0; i < m.len; ++i) {
        fout << m.pos[i] << " ";
    }
    fout << "\n";

    return 0;
}