Cod sursa(job #3217760)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 24 martie 2024 15:53:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <string.h>

const int32_t MAX_LEN = 2000000;

char str1[MAX_LEN + 1], str2[MAX_LEN + 1];
int32_t table[MAX_LEN], res[MAX_LEN];
int main() {
	std::ifstream fin("strmatch.in");
	std::ofstream fout("strmatch.out");

	fin >> str1 >> str2;

	int32_t len1 = strnlen(str1, MAX_LEN);
	int32_t len2 = strnlen(str2, MAX_LEN);

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

	int32_t len = 0, count = 0;
	for(int32_t i = 0; i != len2;) {
		if(str2[i] == str1[len]) {
			++len;
			++i;

			if(len == len1) {
				res[count++] = i - len;
				len = table[len];
			}
		} else {
			len = table[len];
			if(len == -1) {
				++i;
				len = 0;
			}
		}
	}

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

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

	return 0;
}