Cod sursa(job #634585)

Utilizator florin_marius90Florin Marius Popescu florin_marius90 Data 16 noiembrie 2011 18:27:19
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <stdlib.h>



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

	int n, m, pi[2000003];
	char str[2000003], s[2000003];

	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 (c != EOF)
	{
		str[i++] = c;
		m++;
		fscanf(f, "%c", &c);
		
	}


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


	q = 0;
	int sol[1024], id = 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)
		{
			q = pi[q];
			sol[id++] = i - q + 1;
		}
	}

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