Cod sursa(job #1467991)

Utilizator marinutzacatana marina marinutza Data 5 august 2015 03:20:40
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.22 kb
/*Potrivirea sirurilor - KMP*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 2000005

char sir1[NMAX], sir2[NMAX];
int i, j, k, n, m, rez[1005];

int *prefix(char *sir)
{
	int l = strlen(sir);
	int i = 0, j = 0;
	int *pre = (int *)calloc(l+1, sizeof(int));
    for(i = 2; i<=l; ++i)
	{
		while(j && sir[j+1] != sir[i])
			j = pre[j];
		if(sir[j+1] == sir[i])
			++j;
		pre[i] = j;
	}
	return pre;
}

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

    //char *sir1 = (char *)calloc(NMAX, sizeof(char));
    //char *sir2 = (char *)calloc(NMAX, sizeof(char));

	scanf("%s", sir1);
	scanf("%s", sir2);

	n = strlen(sir1);
	m = strlen(sir2);

	memcpy(sir1 + 1, sir1, n*sizeof(char));
	memcpy(sir2 + 1, sir2, m*sizeof(char));

	int *p = prefix(sir1);

	j = 0;
	for(i = 1; i <= m; ++i)
	{
		while( j && sir1[j+1] != sir2[i])
			j = p[j];
		if(sir1[j+1] == sir2[i])
			++j;
		if(j == n)
		{
			j = p[j];
			if(++k > 1000)
				break;
			else
				rez[k] = i - n;
		}
	}

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

	free(prefix);
	//free(sir1);
	//free(sir2);

	return 0;
}