Cod sursa(job #1500435)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 11 octombrie 2015 22:32:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

void make_pi(const string& str, vector<int>& pi){
	const int n = str.size();
	pi.resize(n, 0);
	for(int i = 1; i < n; ++i){
		for(pi[i] = pi[i-1];
			pi[i] && str[i] != str[pi[i]];
			pi[i] = pi[pi[i]-1]);
		if(str[i] == str[pi[i]]){
			++pi[i]; } } }

int main(){
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	string str;
	f >> str;
	const int first_size = str.size();
	str.push_back('#');
	const int st_poz = str.size();
	for(char ch; f >> ch; ){
		str.push_back(ch); }
	vector<int> pi;
	make_pi(str, pi);
	vector<int> rez;
	for(int i = 0; st_poz+i < str.size(); ++i){
		if(pi[st_poz+i] == first_size){
			rez.push_back(i+1-first_size); } }
	g << rez.size() << '\n';
	for(int i = 0; i < 1000 && i < rez.size(); ++i){
		g << rez[i] << ' '; }
	return 0; }