Cod sursa(job #1245583)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 19 octombrie 2014 15:39:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>


std::vector<int> compute_pi(const std::string &subs)
{
    std::vector<int> pi(subs.size(), -1);
    int head = -1;

    for (std::string::const_iterator it = subs.cbegin() + 1;
         it != subs.cend(); ++it) {
        while (head != -1 && subs[head+1] != *it)
            head = pi[head];

        if (subs[head+1] == *it)
            ++head;
        pi[it - subs.cbegin()] = head;
    }

    return pi;
}

int main()
{
    std::ifstream fin("strmatch.in");
    std::ofstream fout("strmatch.out");

    std::string subs;
    char c = fin.get();
    while (fin.good() && c != '\n') {
        subs.push_back(c);
        c = fin.get();
    }

    if (!fin.good()) {
        std::cout << "The input is not in the correct format";
        return 1;
    }

    std::string str;
    c = fin.get();
    while (fin.good() && c != '\n') {
        str.push_back(c);
        c = fin.get();
    }

    std::vector<int> pi = compute_pi(subs);
    int head = -1;
    int total = 0;
    std::vector<int> positions;
    for (std::string::const_iterator it = str.cbegin();
         it != str.cend(); ++it) {
        while (head != -1 && subs[head+1] != *it)
            head = pi[head];

        if (subs[head+1] == *it)
            ++head;

        if (static_cast<unsigned long>(head + 1) == subs.size()) {
            ++total;
            if (total <= 1000)
                positions.push_back(it - str.cbegin() - head);
            head = pi[head];
        }
    }

    fout << total << std::endl;
    for (auto &i : positions)
        fout << i << " ";

    return 0;
}