Cod sursa(job #1336257)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 7 februarie 2015 13:28:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstring>
#define DIM 2000013
using namespace std;
FILE *fin=freopen("strmatch.in","r",stdin);
FILE *fout=freopen("strmatch.out","w",stdout);

char X[DIM], Y[DIM];
int L[DIM], D[DIM], Pos[1003];
int n, m, ap;

void Read()
{
    gets(X);
    gets(Y);
    n = strlen(X);
    m = strlen(Y);
    for(int i = n ; i > 0 ; --i)
        X[i] = X[i - 1];
    for(int i = m ; i > 0 ; --i)
        Y[i] = Y[i - 1];
}

void Build_first()
{
    int k = 0;
    for(int i = 2; i <= n ; ++i)
    {
        while( k > 0 && X[i] != X[k + 1] )
            k = L[k];
        if( X[i] == X[k + 1] )
            ++k;
        L[i] = k;
    }
}

int main()
{
    Read();
    Build_first();
    int k = 0;

    for(int i = 1; i <= m ; ++i)
    {
        while( k > 0 && Y[i] != X[k + 1] )
            k = L[k];
        if( Y[i] == X[k + 1] )
            ++k;
        D[i] = k;
        if( D[i] == n )
        {
            ++ap;
            if( ap <= 1000 )
                Pos[ap] = i - n;
        }
    }

    printf("%d\n", ap);
    for(int i = 1; i <= ap && i <= 1000; ++i)
        printf("%d ", Pos[i]);

    return 0;

}