Cod sursa(job #2424684)

Utilizator nicu97oTuturuga Nicolae nicu97o Data 23 mai 2019 17:50:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_SIZE 2000000
#define MAX_SOL_SIZE 1000

char a[MAX_SIZE];
char b[MAX_SIZE];

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


int* createKMPTable(char* string, int size);

void KMP(char* a, int sizeA, char* b, int sizeB, int* table);

void readChar(char* str, int* len);

int main() {
	int sizeA = 0;
	int sizeB = 0;
	readChar(a, &sizeA);
	readChar(b, &sizeB);
	int* table = createKMPTable(a, sizeA);
	KMP(a, sizeA, b, sizeB, table);
	return 0;
}

void readChar(char* str, int* len) {
	char ch;
	while (true) {
		fin.get(ch);
		if (ch == '\n' || fin.eof()) {
			break;
		}
		str[(*len)++] = ch;
	}
	str[(*len)] = '\0';
}

void KMP(char* a, int sizeA, char* b, int sizeB, int* table) {
	int sol[MAX_SOL_SIZE];
	int j = -1;
	int counter = 0;
	for (int i = 0; i < sizeB; ++i) {
		if (b[i] == a[j + 1]) {
			j++;
		}else {
			while (true) {
				if (j == -1) {
					break;
				}
				j = table[j] - 1;
				if (b[i] == a[j + 1]) {
					j++;
					break;
				}
			}
		}
		if (sizeA == j + 1) {
			if (counter < MAX_SIZE) {
				sol[counter] = i - sizeA + 1;
			}
			counter++;
		}
	}
	fout << counter << '\n';
	int len = counter < MAX_SOL_SIZE ? counter : MAX_SOL_SIZE;
	for (int i = 0; i < len; ++i) {
		fout << sol[i] << ' ';
	}
}

int* createKMPTable(char* string, int size) {
	int* table = (int*)calloc(size, sizeof(int));
	int j = 0;
	for (int i = 0; i < size; ++i) {
		if (i == j) {
			continue;
		}
		if (string[i] == string[j]) {
			table[i] = ++j;
		}
		else {
			j = 0;
			table[i] = 0;
		}
	}
	return table;
}