Cod sursa(job #1604540)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 18 februarie 2016 13:15:30
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

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

void do_strmatch(const string& caut, const string& str, int& rez, vector<int>& poz){
    string s = caut;
    s.append(str);

    vector<int> pi;
    mk_pi(s, pi);

    for(int i = 0, j = caut.size(); j < pi.size(); ++i, ++j){
        if(pi[j] >= caut.size()){
            ++rez;
            if(poz.size() < 1000){
                poz.push_back(i-caut.size()+1);
            }
        }
    }
}

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

    int rez = 0;
    vector<int> poz;

    do_strmatch(caut, str, rez, poz);
    g << rez << '\n';
    for(int i = 0; i < poz.size(); ++i){
        g << poz[i] << ' ';
    }
    return 0;
}