Cod sursa(job #3312946)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 30 septembrie 2025 21:45:52
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <string.h>

const int32_t MAX_LEN = 2000000;
const int32_t MAX_RES = 1000;

char str1[MAX_LEN + 1], str2[MAX_LEN + 1];
int32_t table[MAX_LEN];
int32_t res[MAX_RES], top = 0;

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

	fin >> str1 >> str2;

	int32_t len1 = strlen(str1), len2 = strlen(str2);

	table[0] = -1;
	int32_t pos = -1;
	for(int32_t i = 1; i != len1; ++i) {
		while(pos >= 0 && str1[pos + 1] != str1[i])
			pos = table[pos];
		if(str1[pos + 1] == str1[i])
			++pos;
		table[i] = pos;
	}

	pos = 0;
	for(int32_t i = 0; i != len2; ++i) {
		while(pos >= 0 && str1[pos + 1] != str2[i])
			pos = table[pos];
		if(str1[pos + 1] == str2[i])
			++pos;
		if(pos == len1 - 1 && top != MAX_RES)
			res[top++] = i - len1 + 1;
	}

	fout << top << '\n';
	for(int32_t i = 0; i != top; ++i)
		fout << res[i] << ' ';

	fin.close();
	fout.close();

	return 0;
}