Cod sursa(job #634602)

Utilizator florin_marius90Florin Marius Popescu florin_marius90 Data 16 noiembrie 2011 18:57:33
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.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;
	fscanf(f,"%s", s+1);
	/*while(c != '\n')
	{
		s[i++] = c;
		fscanf(f, "%c", &c);
		
	}*/
	n = strlen(s+1);
	i = 1;
	m = 0;
	fscanf(f, "%s", str+1);
	m = strlen(str+1);
	/*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;
}