Cod sursa(job #489293)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 2 octombrie 2010 10:49:57
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
// infoarena: problema/strmatch //
#include <string.h>
#include <stdio.h>
#define MAXN 2000100

FILE *in, *out;

char a[MAXN],b[MAXN];
int i,j,n,m,l[MAXN],k,q,r[MAXN];

int main()
{
	in = fopen("strmatch.in", "r");
	out = fopen("strmatch.out", "w");
	a[0] = b[0] = ' ';
	fscanf(in, "%s", a+1);
	fscanf(in, "%s", b+1);
	
	n = strlen(a);
	m = strlen(b);
	
	if(n>m)
	{
		fprintf(out, "0");
		return 0;
	}
	
	l[1] = 0;
	for(i=2; i<=n; ++i)
	{
		while(k>0 && a[k+1] != a[i])
			k = l[k];
		if(a[k+1] == a[i])
			++ k;
		l[i] = k;
	}
	
	k=0;
	for(i=1; i<=m-n+k+1; ++i)
	{
		while(a[k+1] != b[i] && k>0)
			k=l[k];
		if(a[k+1] == b[i])
			++ k;
		if(k+1 == n)/
			r[++q] = i-n+1;
	}
	fprintf(out, "%d\n", q);
	
	if(q>1000)
		q=1000;
	for(i=1; i<=q; ++i)
		fprintf(out, "%d ", r[i]);
	
	return 0;
}