Cod sursa(job #1241345)

Utilizator PatrikStepan Patrik Patrik Data 13 octombrie 2014 13:04:56
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
#include<string.h>
#define MAX 2000005
char A[MAX] , B[MAX];
int p[MAX] , N , M  , sol , v[MAX];

int main()
{
	int k , i ;

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

	scanf("%s%s" , A+1 , B+1);
	N = strlen(A+1);
	M = strlen(B+1);
	
	k = 0;
	for(i = 2 ; i <= N ; ++i )
	{
		while(k && A[i] != A[k+1])k = p[k];
		if(A[i] == A[k+1])
			p[i] = ++k;
	}

	k = 0;

	for( i = 1 ; i <= M ; ++i )
	{
		while(k && B[i] != A[k+1])k = p[k];
		if(B[i] == A[k+1])
			k++;
		if(k == N)
		{
			sol++;
			if(sol <= 1000)
				v[sol] = i-N;
		}
	}

	printf("%d\n" , sol );
	for(i = 1 ; i <= sol ; ++i )
		printf("%d " , v[i] );

	return 0;
}