Cod sursa(job #634598)

Utilizator florin_marius90Florin Marius Popescu florin_marius90 Data 16 noiembrie 2011 18:46:25
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
int n, m, pi[2000003];
	char str[2000003], s[2000003];
int sol[2000003], id = 0;

int main()
{
	FILE *f = fopen("strmatch.in","r");
	

	char c;
	fscanf(f, "%c", &c);
	int i = 1;
	while(c != '\n')
	{
		s[i++] = c;
		fscanf(f, "%c", &c);
		
	}
	n = --i;
	i = 1;
	m = 0;
	fscanf(f, "%c", &c);
	while (!feof(f))
	{
		str[i++] = c;
		m++;
		fscanf(f, "%c", &c);
		
	}


	int q = 0;
	pi[1] = 0;
	for (i = 2; i <= n; i++)
	{
		while (q > 0 && s[q+1] != s[i])
			q = pi[q];
		if (s[q+1] == s[i])
			q++;
		pi[i] = q;
	}


	q = 0;
	
	for (i = 1; i <= m; i++)
	{
		while (q > 0 && s[q+1] != str[i])
			q = pi[q];
		if (s[q+1] == str[i])
			q++;
		if (q == n)
		{
			sol[id++] = i - q;
			//printf("i = %i, q = %i", i,q);
			q = pi[q];
		}
	}

	fclose(f);
	f = fopen("strmatch.out","w");
	fprintf(f, "%i\n", id);
	for (i = 0; i < id; i++)
		fprintf(f, "%i ", sol[i]);
	fclose(f);
	return 0;
}