Cod sursa(job #2139784)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 22 februarie 2018 19:51:38
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

const int N = 4e6 + 5;

vector<int> ans;
int z[N];

static int zet(string &str) {
	memset(z, 0x00, sizeof(int) * (str.size() + 5));
	int n, l = 0, r = 0;

	n = str.size();
	for (int i = 1; i < n; ++i) {
		if (i > r) {
			for (int j = 0; j < n - i && str[j] == str[i + j]; ++j)
				z[i]+= 1;
			l = i;
			r = i + z[i]; }
		else {
			z[i] = min(r - i, z[i - l]);
			for (int j = z[i]; j < n - 1 && str[j] == str[i + j]; ++j)
				z[i]+= 1;
			if (i + z[i] > r) {
				r = i + z[i];
				l = i; } } }

	return z[str.size() - 1]; }

int main() {
	string str, pat;

	fi >> pat >> str;
	str = pat + "#" + str;

	zet(str);
	for (int i = 1; i < str.size(); ++i) if (z[i] == pat.size())
		ans.push_back(i - pat.size() - 1);

	fo << ans.size() << '\n';
	for (int i = 0; i < 1000 && i < ans.size(); ++i)
		fo << ans[i] << ' ';
	fo << endl;

	return 0; }