Cod sursa(job #1455619)

Utilizator aimrdlAndrei mrdl aimrdl Data 28 iunie 2015 17:08:38
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define MAX 2000000

int *computePi (char *s) {
	int l = strlen(s);
	int *pi = new int[l];
	pi[0] = 0;
	int k = 0;
	
	for (int i = 1; i < l; ++i) {
		while (k > 0 && s[i] != s[k]) {
			k = pi[k];
		}
		
		if (s[i] == s[k]) ++k;
		
		pi[i] = k;
	}
	
	return pi;
}

int strMatch (char *target, char *source, vector <int> & v) {
	int *pi = computePi(target);	
		
	int lt = strlen(target), ls = strlen(source), k = 0, matchesNo = 0;

	for (int i = 0; i < ls; ++i) {
		while (k > 0 && target[k] != source[i]) {
			k = pi[k];
		}
		
		if (target[k] == source[i]) ++k;
		
		if (k == lt) {
			++matchesNo;
			v.push_back(i - lt + 1);
			k = pi[k-1];
		}
	}
	
	delete[] pi;
	return matchesNo;
}
 
int main (void) {
	FILE *in = fopen("strmatch.in", "r");
	char *buffer = new char[MAX];
	
	fgets(buffer, MAX, in);
	buffer[strlen(buffer) - 1] = '\0';
	char *s1 = strdup(buffer);
	
	fgets(buffer, MAX, in);
	buffer[strlen(buffer) - 1] = '\0';
	char *s2 = strdup(buffer);
	
	delete[] buffer;
	fclose(in);
	
	FILE *out = fopen("strmatch.out", "w");
	  
	vector <int> v;
	int matchesNo = strMatch(s1, s2, v);
	fprintf(out, "%d\n", matchesNo);
	
	for (int i = 0; i < matchesNo && i < 2000; ++i) {
		fprintf(out, "%d ", v[i]);
	} 
	
	
	delete[] s1;
	delete[] s2;
	v.clear();	
	fclose(out);
	return 0;
}