Cod sursa(job #723792)

Utilizator gener.omerGener Omer gener.omer Data 25 martie 2012 20:42:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <vector>
#include <climits>
#include <set>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <cstring>

#define NMAX 2000005

using namespace std;

char T[NMAX], P[NMAX];
int b[NMAX];
int pos[1000];

void citire(){
	ifstream in("strmatch.in"); 
	in >> P;
	in >> T;
}

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

int nr_apar = 0;

void scrie_sol(){
	ofstream out("strmatch.out");
	int i;
	out << nr_apar << endl;
	for(i = 0; i < nr_apar; ++i)
		out << pos[i] << " ";
}

int main(){
	citire();
	compute_prefix();
	int j = 0, i;
	
	for(i = 0; i < strlen(T);){
		while(j >= 0 && P[j] != T[i])
			j = b[j];
		++j, ++i;
		if(j == strlen(P)){
			pos[nr_apar] = i - strlen(P);
			nr_apar++;
			if(nr_apar == 1000)
				goto scrie;
			j = b[j];
		}
	}

scrie:	
	scrie_sol();
	
	return 0;
}