Cod sursa(job #1748090)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 26 august 2016 06:42:15
Problema Potrivirea sirurilor Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 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] = ((i != n-1 && str[k+1] == str[i+1]) ?  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;

	const int n = str.size(), m = pat.size();

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

	int nr_match = 0;
	vector<int> rez;

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

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

	return 0; }