Cod sursa(job #360899)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 2 noiembrie 2009 19:56:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
#include<string.h>

char m[2000100],n[2000100];
int i,k,ln,lm,pi[2000100],p[1010],nr;

void prefix()
{ int k=0;
  pi[1]=0;
  for(i=2;i<=ln;i++) { while(k>0&&n[k+1]!=n[i]) k=pi[k];
                       if(n[k+1]==n[i]) k++;
                       pi[i]=k;
                     }		
}

void kmp()
{ 
	int k=0;
	
	for(i=1;i<=lm;i++) { while(k>0&&n[k+1]!=m[i]) k=pi[k];
	                     if(n[k+1]==m[i]) k++;
	                     if(k==ln) { nr++;
						             if(nr<=1000) p[nr]=i-ln;
						           }
	                   }
	printf("%d\n",nr);
	if(nr>1000) nr-=1000;
	for(i=1;i<=nr;i++) printf("%d ",p[i]);
    printf("\n");
}	

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	scanf("%s",n+1);
	scanf("%s",m+1);
	
	ln=strlen(n+1);
	lm=strlen(m+1);
	if(n[ln]=='\n') ln--;
	if(m[lm]=='\n') lm--;
	
	prefix();
	kmp();

    fclose(stdin);
    fclose(stdout);
    
    return 0;
}