Cod sursa(job #157776)

Utilizator cos_minBondane Cosmin cos_min Data 13 martie 2008 11:35:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>

#define in "strmatch.in"
#define out "strmatch.out"
#define dim 2000013

inline int Minim(int a, int b) {
       if ( a < b ) return a;
       return b;
}

int N, M, nrSol=0;
int Pi[dim], Sol[1001];
char A1[dim], A2[dim];

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    N = M = 0;
    fgets( A1, dim-1, stdin );
    fgets( A2, dim-1, stdin );
    
    while ( (A1[N] >= 'a' && A1[N] <= 'z') || (A1[N] >= 'A' && A1[N] <= 'Z') || (A1[N] >= '0' && A1[N] <= '9') ) N++;
    while ( (A2[M] >= 'a' && A2[M] <= 'z') || (A2[M] >= 'A' && A2[M] <= 'Z') || (A2[M] >= '0' && A2[M] <= '9') ) M++;
    
    for ( int i = N; i; i-- ) A1[i] = A1[i-1];
    for ( int i = M; i; i-- ) A2[i] = A2[i-1];
    
    int K;
    Pi[1] = K = 0;
    
    for ( int i = 2; i <= N; i++ )
    {
        while ( K && A1[K+1] != A1[i] ) K = Pi[K];
        if ( A1[K+1] == A1[i] ) K++;
        Pi[i] = K; 
    }
    
    K = 0;
    for ( int i = 1; i <= M; i++ )
    {
        while ( K && A1[K+1] != A2[i] ) K = Pi[K];
        if ( A1[K+1] == A2[i] ) K++;
        
        if ( K == N )
        {
             nrSol++;
             nrSol<1001?Sol[nrSol]=i-N:1;
        }
    }
    
    printf("%d\n", nrSol);
    for ( int i = 1; i <= Minim(nrSol,1000); i++ )
        printf("%d ", Sol[i]);
}