Cod sursa(job #156726)

Utilizator ninjaNo name ninja Data 12 martie 2008 18:33:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>

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

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

int main()
{
    FILE *fin = fopen(in,"r");
    freopen(out,"w",stdout);
    
    fgets(A1,dim-1,fin);
    fgets(A2,dim-1,fin);
    
    N = M = 0;
    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 j = M; j; j-- ) A2[j] = A2[j-1];
    
    Pi[1] = 0;
    for ( int i = 2, k = 0; i <= N; i++ )
    {
        while (k && A1[k+1] != A1[i]) k = Pi[k];
        if ( A1[k+1] == A1[i] ) k++;
        Pi[i] = k;
    }
    
    for ( int i = 1, k = 0; i <= M; i++ )
    {
        while(k && A1[k+1] != A2[i]) k = Pi[k];
        if ( A1[k+1] == A2[i] ) k++;
        
        if (k == N) 
        {
              k = Pi[k], nrSol++;
              if ( nrSol <= 1000 ) Sol[nrSol] = i-N;
        }
    }
    
    
    printf("%d\n", nrSol);
    for ( int i = 1; i <= (nrSol<1000?nrSol:1000); i++ )
        printf("%d ", Sol[i]);
}