Cod sursa(job #3220356)

Utilizator DumitrescuADumitrescuA DumitrescuA Data 3 aprilie 2024 12:37:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <string.h>

const int32_t MAX_LEN = 2000000;
const int32_t MAX_OUT = 1000;

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 pos = 0, count = 0;
	for(int32_t i = 0; i != len2;) {
		if(str2[i] == str1[pos]) {
			++pos;
			++i;

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

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

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

	return 0;
}