Cod sursa(job #298102)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 5 aprilie 2009 20:50:06
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#include<string.h>
#define LMAX 2000002
char s[LMAX],p[LMAX],n,m;
int pi[LMAX],i,numar;
int main(void)
{

freopen("strmatch.in","r",stdin); 
freopen("strmatch.out","w",stdout);
scanf("%s%s",p+1,s+1);  
n=strlen(s+1);
m=strlen(p+1); 

int *v=new int[n/m+1];
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++;
        v[numar]=i-m;
        q=pi[q];   
        }   
    }
printf("%d\n",numar);
for(i=1;i<=numar;i++)
    printf("%d ",v[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;      
}