Cod sursa(job #1748083)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 26 august 2016 06:26:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;

vector<int> mk_kmp_shift(const string& str){
	const int n = str.size();
	vector<int> bord(n, 0), strong_bord(n, 0);
	for(int i = 1, k = 0; i < n; ++i){
		for( ; k && str[k] != str[i]; k = bord[k-1]);
		if(str[k] == str[i]){
			++k; }
		bord[i] = k;
		strong_bord[i] = (str[k] == str[i] ?  strong_bord[k-1] : k); }
	for(int i = 0; i < n; ++i){
		strong_bord[i] = i - strong_bord[i] + 1; }
	return strong_bord; }

int main(){
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	string pat, str;

	f >> pat >> str;

	char cur;

	auto shift = mk_kmp_shift(pat);
	int i_str = 0, i_pat = 0;

	int nr_match = 0;
	vector<int> rez;

	while(i_str < str.size()){
		int j = 0;
		while(j < pat.size() && pat[i_pat + j] == str[i_str + j]){
			++j; }
		if(j == pat.size()){
			if(nr_match++ < 1000){
				rez.push_back(i_str); } }
		if(i_pat == 0){
			++i_str; }
		else{
			i_str += shift[i_pat-1];
			i_pat -= shift[i_pat-1]; } }

	g << nr_match << '\n';
	for(const auto x : rez){
		g << x << ' '; }

	return 0; }