Cod sursa(job #1391889)

Utilizator PatrikStepan Patrik Patrik Data 18 martie 2015 11:19:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<string.h>

#define LMAX 2000001

char N[LMAX] , M[LMAX];
int pi[LMAX] , n , m , sol[LMAX];

void prefix();
void solve();


int main()
{

	freopen("strmatch.in" , "r" , stdin );
	freopen("strmatch.out" , "w" , stdout );
	scanf("%s%s" , N+1 , M+1);
	n = strlen(N+1);
	m = strlen(M+1);

	prefix();
	solve();

	printf("%d\n" , sol[0]);
	for(int i = 1 ; i <= sol[0] && i <= 1000 ; ++i )
		printf("%d " , sol[i]);

	return 0;
}

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

void solve()
{
	int k = 0;
	for(int i = 1 ; i <= m; ++i ){
		while(k && M[i] != N[k+1])
			k = pi[k];
		if(M[i] == N[k+1])
			k++;
		if(k == n)
			sol[++sol[0]] = i-n;
	}
}