Cod sursa(job #950648)

Utilizator mihaionlyMihai Jiplea mihaionly Data 17 mai 2013 14:29:39
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define uint unsigned
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define NMAX 2000000
#define max(x,y) ((x>y)?(x):(y))
char S[NMAX],P[NMAX];
int p[NMAX];
vector<int> v;
//Prefix vector:
void prefix() {
	
	uint i,j;
	p[0] = -1;
	for(j=0,i=1; i<strlen(P); i++) {
		if(j < strlen(P) && P[i]==P[j]) {
			//It's a match:
			p[i] = j;
			j++;
		} else {
			//Not a match:
			p[i] = -1;
			j=0;
		}
	}

//	for(i=0;i<strlen(P);i++) g<<p[i]<<" ";g<<"\n";
}

void KMP() {
	int lengthP = strlen(P), lengthS = strlen(S);
	int i,j;
	j = -1;
	i = 0;
	while(i < lengthS - lengthP + 1) {
		
		while(j!= -1 && P[j+1] != S[i]) {
			j = p[j];
		}
		
		while(i < lengthS && j+1 < lengthP && S[i] == P[j+1]) {
			++j;
			++i;
		}
		
		if(j == lengthP - 1) {// we have a solution
			v.push_back(i-j-1);
			j = p[j];
			//++i;
		} else {
			//g<<"I am here";
			i++;
			j=-1;
		}
		//g<<i<<" "<<j<<"\n";

	}
	//g<<"\n";
	
}

void print_solutions() {
	g<<v.size()<<"\n";
	for(uint i=0; i < v.size(); i++)
		g<<v[i]<<" ";
	
}

int main() {
	
	f.getline(P, NMAX);
	f.getline(S, NMAX);
	if(strlen(P)<=strlen(S)) {
		prefix();
		KMP();
	}
	print_solutions();
	return 0;
}