Cod sursa(job #1585244)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 30 ianuarie 2016 21:18:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <string.h>
#include <stdio.h>

#define MAXN 2000003

char X[MAXN], Y[MAXN];
int Pi[MAXN], d[MAXN];
int i, K, N, M, ct;

void constructie_pi() //constructia pi-ului
{
	N = strlen(X)-1;
	K = 0;	   // iteratorul K care ne ajuta la contructia lui Pi
	Pi[1] = 0; // Pi[i] < i => Pi[1] = 0
	for (i = 2; i <= N; ++i){
		while (K > 0 && X[i] != X[K+1]) // cat timp prefixul nu este nul si literele
			K = Pi[K];					// nu coincid sar din K in Pi[K]
		if (X[i] == X[K+1]) K = K + 1;  // daca literele coicid
		Pi[i] = K;
	}
}

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

	fgets(X+1, MAXN, stdin);
	fgets(Y+1, MAXN, stdin);
	X[0] = ' '; Y[0] = ' ';
	X[strlen(X)-1] = Y[strlen(Y)-1] = 0;

	M = strlen(Y)-1;
	constructie_pi();
	K = 0;
	for (i = 1; i <= M; ++i){
		while (K > 0 && Y[i] != X[K+1]) // cat timp prefixul nu este nul si literele
			K = Pi[K];					// nu coincid sar din K in Pi[K]
		if (Y[i] == X[K+1]) K = K + 1;  // daca literele coincid
		d[i] = K;
		if(d[i]==N)ct++;
	}
	printf("%d\n",ct);
	for (i = 1;  i <= M; ++i)
		if (d[i] == N) 				// daca d[i] == N inseamna ca intreg sirul X coincide
			printf("%d ", i-N);   // cu sufixul lui Yi
	return 0;

}