Cod sursa(job #508226)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 7 decembrie 2010 21:38:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max 2000002

char p[max],t[max];
int n,m,i,k,nr,l[max],sol[1001];

int main () {
	freopen("grader_test50.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(p+1,max,stdin);
	fgets(t+1,max,stdin);
	n=strlen(p+1)-1;
	m=strlen(t+1)-1;	

	l[1]=0;
    for (i=2; i<=n; i++) {
		k=l[i-1];
	    while (k>0 && p[i]!=p[k+1]) k=l[k];
        if (p[i]==p[k+1]) k++;
	    l[i]=k;
	}
	k=0;
	nr=0;
    for (i=1; i<=m; i++) { 
		while (k>0 && t[i]!=p[k+1]) k=l[k];
		if (t[i]==p[k+1]) k++;
        if (k==n) {        
			nr++;
            if (nr<=1000) sol[nr]=i-n;
			k=l[n];
	    }
	}
	printf("%d\n",nr);
	if (nr>1000) nr=1000;
	for (i=1; i<=nr; i++) printf("%d ",sol[i]);
	return 0;
}