Cod sursa(job #160651)

Utilizator marinaMarina Horlescu marina Data 16 martie 2008 14:53:56
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
//Potrivirea sirurilor - KMP
#include <stdio.h>
#define INPUT "strmatch.in"
#define OUTPUT "strmatch.out"
#define MAX 2000001
#define AMAX 1001

char A[MAX], B[MAX];
int T[MAX], poz[AMAX];
int nr;

void prefix()
{
	int i, k = -1;
	T[0] = -1;
	for(i = 1; A[i]; ++i)
	{
		while(k >= 0 && A[i] != A[k+1])
			k = T[k];
		if(A[i] == A[k+1]) ++k;
		T[i] = k;
	}
}

void potrivire()
{
	int i, k = -1;
	for(i = 0; B[i]; ++i)
	{
		while(k >= 0 && B[i] != A[k+1])
			k = T[k];
		if(B[i] == A[k+1]) ++k;
		if(k>0 && !A[k+1])
		{
			if(nr < 1000) poz[++nr] = i-k;
			if(nr == 1000) return;
		}			
	}
}

void afis()
{
	int i;
	printf("%d\n", nr);
	for(i = 1; i < nr; ++i)
		printf("%d ", poz[i]);
	printf("%d\n", poz[nr]);
}
int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%s\n", A);
	scanf("%s\n", B);

	prefix();
	potrivire();
	afis();
	
	return 0;
}