Cod sursa(job #298145)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 5 aprilie 2009 21:20:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<string.h>
#define LMAX 2000002
char s[LMAX],p[LMAX];
int i,numar,n,m,pi[LMAX];
int v[1010];

int main(void)
{

freopen("strmatch.in","r",stdin); 
freopen("strmatch.out","w",stdout);
scanf("%s",p+1);
scanf("%s",s+1);  
n=strlen(s+1);
m=strlen(p+1); 
//int *pi=new int[(m+1)*sizeof(int)];
pi[1]=0;
int k=0;
for(i=2;i<=m;i++)
    {
    while(k>0&&p[k+1]!=p[i])
        k=pi[k];
    if(p[k+1]==p[i])
        k++;
    pi[i]=k;    
    }
int q=0;

for(i=1;i<=n;i++)
    {
    while(q>0&&p[q+1]!=s[i])
        q=pi[q];
    if(p[q+1]==s[i])
        q++;
    if(q==m)
        {
        numar++;
        if(numar<=1000)
            {
            v[numar]=i-m;
            }
        q=pi[q];   
        }   
    }
printf("%d\n",numar);
numar=numar>1000?1000:numar;
for(i=1;i<=numar;i++)
    printf("%d ",v[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;      
}