Cod sursa(job #748552)

Utilizator IeewIordache Bogdan Ieew Data 13 mai 2012 18:48:28
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
#include <string.h>
char a[2000002];
char b[2000002];
int n,m;
int app[1024], k;
int next[2000000];

void calc_next()
{
	int i,j = 0;
	
	for(i = 1;i < n;i++)
	{
		while( j && a[j] != a[i])
			j = next[j];
		if(a[j] == a[i])
			j++;
		next[i] = j;
	}
}

inline int minim(int a, int b)
{	return a<=b?a:b;}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	fgets(a, sizeof(a), stdin);
	fgets(b, sizeof(b), stdin);
	n = strlen(a);
	m = strlen(b);
	a[--n] = 0;
	b[--m] = 0;
	calc_next();
	int i,j = 0;

	for(i=0;i<m;i++)
	{
		while(j && b[i] != a[j])
			j = next[j - 1];
		if( b[i] == a[j])
			j++;
		if(j==n )
		{
			j = next[n - 1];
			if(k < 1000)
				app[k] = i - n +1;
			k++;
		}
	}
	
	printf( "%d\n",k);
	int x = minim(1000,k);
	for(i=0;i< x;i++)
		printf( "%d ", app[i]);	
	printf("\n");
	return 0;
}