Cod sursa(job #757399)

Utilizator igsifvevc avb igsi Data 11 iunie 2012 22:46:46
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.99 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; 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[0];
			if(matches[0] <= 1000) matches[matches[0]] = i - wordL + 1;
		}
	}
	
	fprintf(out, "%d\n", matches[0]);
	k = (1000 < matches[0] ? 1000 : matches[0]);
	for(i = 1; i <= k; i++) fprintf(out, "%d ", matches[i]);
	fprintf(out, "\n");
	
	fclose(in);
	fclose(out);
	return 0;
}