Cod sursa(job #2348832)

Utilizator TheNechizFMI Razvan Birisan TheNechiz Data 20 februarie 2019 00:36:18
Problema Potrivirea sirurilor Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include<stdio.h>
#include<string.h>
#define LSir 2000010
#define NMax 1024

char A[LSir],B[LSir];
int lA,lB,Urm[LSir],Apar[NMax],nApar;

void Urmatorul( char *P , int lP)
{
    int k=0,x;
    Urm[1]=0;
    for(x=2;x<lP;x++)
    {
        while(k>0 && P[k+1]!=P[x])
            k=Urm[k];
        if(P[k+1]==P[x]) k++;
        Urm[x]=k;
    }
}
int ok( char a )
{
    return (a>='a' && a<='z')||(a>='A'&&a<='Z')||(a>='0'&&a<='9');
}
int LungSir( char *s )
{
    int i;
    for(i=1;s[i];i++)
        if( !ok(s[i]) )
            break;
    s[i]='\0';
    return i;
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    int i,x=0;
    
    fgets(A+1,LSir,stdin);
    fgets(B+1,LSir,stdin);
    lA=LungSir(A);
    lB=LungSir(B);
    Urmatorul(A,lA);
    for(i=1;i<lB;i++)
    {
        while(x>0 && A[x+1]!=B[i])
            x=Urm[x];
        if(A[x+1]==B[i])
            x++;
        if(x==lA-1)
        {
            if( nApar <= 1000 )
                Apar[++nApar]=i-lA+1;
            else
                nApar++;
            
            x=Urm[x];
        }
    }
    if( nApar <= 1000 )
    {
        printf("%d\n",nApar);
        for(i=1;i<=nApar;i++)
            printf("%d ",Apar[i]);
    }
    else
    {
        printf("%d\n",nApar);
        for(i=1;i<=1000;i++)
            printf("%d ",Apar[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}