Cod sursa(job #688085)

Utilizator gener.omerGener Omer gener.omer Data 22 februarie 2012 23:45:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NMAX 2000005
char T[NMAX], P[NMAX];
int b[NMAX];

void citire(){
	FILE * f = fopen("strmatch.in", "rt");
	fscanf(f, "%s %s", P, T);
	fclose(f);
}

void compute_prefix(){
	b[0] = -1;
	int k = -1;
	for(unsigned i = 0; i < strlen(P);){
		while(k >= 0 && P[i] != P[k])
			k = b[k];
		++k, ++i;
		b[i] = k;
	}
}
vector<int> aparitii;

void scrie_sol(){
	FILE* f = fopen("strmatch.out", "wt");
	fprintf(f, "%d\n", aparitii.size());
	for(unsigned i = 0; i < aparitii.size() && i < 1000; ++i)
		fprintf(f, "%d ", aparitii[i]);
	fclose(f);
}

int main(){
	citire();
	compute_prefix();
	int j = 0;
	
	for(unsigned i = 0; i < strlen(T);){
		while(j >= 0 && P[j] != T[i])
			j = b[j];
		++j, ++i;
		if(j == strlen(P)){
			aparitii.push_back(i - strlen(P));
			j = b[j];
		}
	}
	scrie_sol();
	
	return 0;
}