Cod sursa(job #1834385)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 24 decembrie 2016 15:06:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

// Strings are indexed from 1, and start with a garbage character like #
vector<int> get_lens(const string& small, const string& big) {
	string huge = small + big;
	vector<int> ans(big.length()), z(huge.length());
	int N = huge.length()-1, l = 0, r = 0;
	for (int i = 2; i <= N; ++i) {
		if (r >= i) {
			z[i] = min(r-i+1, z[i-l+1]);
		}

		while (i+z[i] <= N && huge[i+z[i]] == huge[1+z[i]])
			++z[i];

		if (i + z[i]-1 > r) {
			l = i;
			r = i+z[i]-1;
		}
	}

	for (int i = small.length()+1; i <= N; ++i) {
		ans[i-small.length()] = z[i];
	}

	return ans;
}

int main() {
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	string s, S;
	fin >> s >> S;
	s = "#" + s;
	S = "#" + S;
	auto len = get_lens(s, S);
	int ans = 0;
	for (int i = 1; i < S.length(); ++i) {
		if (len[i] == s.length()-1)
			++ans;
	}
	fout << ans << "\n";
	ans = 0;
	for (int i = 1; i < S.length() && ans < 1000; ++i) {
		if (len[i] == s.length()-1) {
			++ans;
			fout << i-1 << " ";
		}
	}
}