Cod sursa(job #146589)

Utilizator andrei_infoMirestean Andrei andrei_info Data 1 martie 2008 21:58:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 2000010
char s1[MAX], s2[MAX];
long match[1000], l1, l2, nr_m, pi[MAX];

void prefix()
{
	long i, k =0;
	pi[0] = 0;
	for (i = 2; i<=l1; i++)
	{
		while ( k > 0 && s1[k+1] != s1[i])
			k = pi[k];
		if ( s1[k+1] == s1[i] )
			k++;
		pi[i] = k;
	}
}

void solve()
{
	long k =0 ;
	for ( int i = 1; i<=l2; i++)
	{
		while ( k > 0 && s1[k+1] != s2[i] )
			k = pi[k];
		if ( s1[k+1] == s2[i])
			k++;
		if ( k == l1 )
		{
			nr_m++;
			if (nr_m <= 1000) match[nr_m] = i-l1;
		}
	}
}


int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	scanf("%s", s1+1);
        scanf("%s", s2+1);
	l1 = strlen(s1+1);
	l2 = strlen(s2+1);

	prefix();
	solve();

	printf("%ld\n", nr_m);

	for (int i = 1; i<=nr_m && i<=1000; i++)
		printf("%ld ", match[i]);

	return 0;
}