Cod sursa(job #949631)

Utilizator mihaionlyMihai Jiplea mihaionly Data 14 mai 2013 14:47:45
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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 A[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;
		}
	}

	
}

void KMP() {
	uint lengthP = strlen(P), lengthA = strlen(A);
	uint i,j;
	for(j=0, i=0; i < lengthA - lengthP + 1; i++) {
		while(P[j] != A[i+j] && p[j] != -1) {
			j = p[j];
		}
		
		while(j < lengthP && i+j < lengthA  && A[i+j] == P[j]) {
			++j;
		}
		if(j == strlen(P)) {// we have yet another sollution
			v.push_back(i);
			j = max(0, p[j]);
		} else
			j = 0;
	}
	
}

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(A, NMAX);
	
	prefix();
	KMP();
	print_solutions();
	return 0;
}