Cod sursa(job #2740352)

Utilizator muiepulicimatacutactu muiepulici Data 12 aprilie 2021 18:01:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <cstring>
#include <fstream>

int LPS[2000001];

void BuildLPS(char* pattern, int m) {
	LPS[0] = 0;

	int i = 1, j = 0;

	while (i < m) {
		if (pattern[i] == pattern[j])
			LPS[i++] = ++j;
		else {
			if (j != 0)
				j = LPS[j - 1];
			else
				LPS[i++] = 0;
		}
	}
}

int N = 0;
int poz[1000];

void KMP(char* text, char* pattern) {
	int m = strlen(pattern);

	BuildLPS(pattern, m);

	int n = strlen(text);

	int i = 0, j = 0;

	while (i < n) {
		if (text[i] == pattern[j]) {
			++i;
			++j;

			if (j == m) {
				poz[N++] = i - j;
				j = LPS[j - 1];
			}
		} else {
			if (j != 0)
				j = LPS[j - 1];
			else
				++i;
		}
	}
}

char A[2000001];
char B[2000001];

int main() {			  
	std::ifstream fin("strmatch.in");
	std::ofstream fout("strmatch.out");

	fin >> A >> B;

	fin.close();

	KMP(B, A);

	fout << N << '\n';

	for (int i = 0; i < N; ++i)
		fout << poz[i] << ' ';
	fout << '\n';

	fout.close();

	return 0;
}