Cod sursa(job #1347369)

Utilizator rockerboyHutter Vince rockerboy Data 18 februarie 2015 22:18:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <string>
#include <vector>

std::ifstream be ("strmatch.in");
std::ofstream ki ("strmatch.out");

std::string s, szo;
std::vector<int> pre, megold;
int hs, hszo;

void make_pre()
{
    int last = 0;
    pre.resize (hszo+1, 0);
    pre[1] = 0;
    for (int i=2; i<=hszo; i++) {
        while (last != 0 && szo[last+1] != szo[i])
            last = pre[last];
        //if (last) last++;
        if (szo[last+1] == szo[i]) last++;
        pre[i] = last;
    }
}

void kmp()
{
    int last = 0;
    for (int i=1; i<=hs; i++) {
        while (last != 0 && s[i] != szo[last+1]) last = pre[last];
        //if (last) last++;
        if (s[i] == szo[last+1]) last++;
        if (last == hszo) {
            last = pre[last];
            megold.push_back (i-hszo);
        }
    }
}

int main()
{
    be >> szo >> s;
    hs = s.length();
    hszo= szo.length();
    s.insert (0, " ");
    szo.insert (0, " ");

    make_pre();
    //for (int i=1; i<=hszo; i++) ki << pre[i];
    kmp();

    ki << megold.size() << "\n";
    int sz = megold.size(); if (sz > 1000) sz = 1000;
    for (int i=0; i<sz; i++) ki << megold[i] << " ";
}