Cod sursa(job #757394)

Utilizator igsifvevc avb igsi Data 11 iunie 2012 22:37:41
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXL 2000002

int prefix[MAXL], matches[1001];
char word[MAXL], search[MAXL];

int main()
{
	FILE *in = fopen("strmatch.in", "r");
	FILE *out = fopen("strmatch.out", "w");
	int wordL, searchL, i, k;
	
	fscanf(in, "%s\n%s", word, search);
	wordL = strlen(word);
	searchL = strlen(search);
	
	k = -1;
	prefix[0] = k;
	for(i = 1; i < wordL; i++)
	{
		while(k != -1 && word[k + 1] != word[i]) k = prefix[k];
		if(word[k + 1] == word[i]) k++;
		prefix[i] = k;
	}
	
	k = -1;
	matches[0] = 0;
	for(i = 0; i < searchL && matches[0] < 1000; i++)
	{
		while(k != -1 && word[k + 1] != search[i]) k = prefix[k];
		if(word[k + 1] == search[i]) k++;
		if(k == wordL - 1)
		{
			k = prefix[k];
			matches[++matches[0]] = i - wordL + 1;
		}
	}
	
	fprintf(out, "%d\n", matches[0]);
	for(i = 1; i <= matches[0]; i++) fprintf(out, "%d ", matches[i]);
	fprintf(out, "\n");
	
	fclose(in);
	fclose(out);
	return 0;
}