Cod sursa(job #512432)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 13 decembrie 2010 21:27:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<stdio.h>
#include<string.h>

#define LMT 2000006

char s[LMT];
char p[LMT];
int pi[LMT];
int n,m,nrp;
int poz[1006];

int main ()
{
    int i,q=0;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    s[0]=p[0]=' ';
    fgets(p+1,sizeof(p)-1,stdin);
    fgets(s+1,sizeof(s)-1,stdin);

    n=strlen(s+1);
    m=strlen(p+1);

    while(!((s[n]>='a' && s[n]<='z')
    || (s[n]>='A' && s[n]<='Z')
    || (s[n]>='0' && s[n]<='9')))
        n--;
        
    while(!((p[m]>='a' && p[m]<='z')
    || (p[m]>='A' && p[m]<='Z')
    || (p[m]>='0' && p[m]<='9')))
        m--;

    for(i=2;i<=m;i++)
    {
        while(q>0 && p[q+1]!=p[i])
            q=pi[q];
        if(p[q+1]==p[i])
            q++;
        pi[i]=q;
    }
    q=0;
    for(i=1;i<=n;i++)
    {
        while (q>0 && s[i]!=p[q+1])
            q=pi[q];
        if (s[i]==p[q+1])
            q++;
        if (q==m)
        {
            poz[++nrp]=i-m;
            if(nrp==1000)
                break;
            q=pi[q];
        }
    }
    printf("%d\n",nrp);
    for(i=1;i<=nrp;i++)
        printf("%d ",poz[i]);
    printf("\n");
    return 0;
}