Cod sursa(job #1489518)

Utilizator alexandru.huleaAlexandru Hulea alexandru.hulea Data 21 septembrie 2015 13:39:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX 2000010
#define MAX_PRINT 1000

int* pi;
int* pozitii;
int nr;

using namespace std;

void prefix(char* sir) {
	int n = strlen(sir);
	int k = -1;
	pi[0] = -1;

	for (int i = 1; i < n; i++) {
		while (k > -1 && sir[k + 1] != sir[i]) {
			k = pi[k];
		}
		if (sir[k + 1] == sir[i]) {
			k++;
		}
		pi[i] = k;
	}
}

void kmp(char* cautat, char* sir) {
	int lungimeCautat = strlen(cautat);
	int lungimeSir = strlen(sir);
	int q = -1;
	for (int i = 0; i < lungimeSir; i++) {
		while (q > -1 && cautat[q + 1] != sir[i]) {
			q = pi[q];
		}
		if (cautat[q + 1] == sir[i]) {
			q++;
		}
		if (q + 1 == lungimeCautat) {
			pozitii[nr] = i - lungimeCautat + 1; 
			nr++;
		}
	}
}

int main() {

	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	char* a = new char[MAX];
	char* b = new char[MAX];

	scanf("%s", a);
	scanf("%s", b);

	nr = 0;
	pozitii = new int[MAX_PRINT];
	pi = new int[MAX];

	prefix(a);
	kmp(a, b);
	printf("%i\n", nr);
	for (int i = 0; i < nr; i++) {
		printf("%i ", pozitii[i]);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}