Cod sursa(job #1455645)

Utilizator aimrdlAndrei mrdl aimrdl Data 28 iunie 2015 18:04:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define MAX 2000005

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 && s[i] != s[k]) {
			k = pi[k - 1];
		}
		
		if (s[i] == s[k]) ++k;
		
		pi[i] = k;
	}
	
	return pi;
}

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