Cod sursa(job #1571887)

Utilizator alexandru92alexandru alexandru92 Data 18 ianuarie 2016 16:51:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <array>
#include <string>
#include <vector>
#include <limits>
#include <fstream>
#include <iterator>
#include <algorithm>

using std::pair;
using std::array;
using std::string;
using std::vector;

const int NMAX = 2000011;
const int NUM_MAX_OF_MATCHES = 1000;

vector<int> ZValues(const string& P) {
    vector<int> Z(P.size());

    for (int k = 0, lt = 0, rt = 0; k < P.size(); ++k) {
        if (k > rt) {
            int i;
            for (i = 0; i + k < P.size() && P[i] == P[i + k]; ++i);
            Z[k] = i;
            if (i) {
                lt = k;
                rt = i + k - 1;
            }
        }
        else {
            int p = k - lt;
            if (Z[p] < rt - k + 1) {
                Z[k] = Z[p];
            }
            else {
                int i;
                for (i = rt + 1; i < P.size() && P[i] == P[i - k]; ++i);
                Z[k] = i - k;
                lt = k;
                rt = i - 1;
            }
        }
    }

    return Z;
}

pair<int, vector<int>> strMatch(const string& P, const string& T) {
    if (P.size() > T.size()) {
        return std::make_pair(0, vector<int>{});
    }
    else if (P.size() == T.size()) {
        return P != T ? std::make_pair(0, vector<int>{}) : std::make_pair(1, vector<int>{0});
    }

    vector<int> Z = ZValues(P);
    vector<int> sp(P.size());

    for (int j = P.size() - 1; j >= 1; --j) {
        int i = j + Z[j] - 1;
        if (i < sp.size()) {
            sp[i] = Z[j];
        }
    }

    int numMatches = 0;
    vector<int> matches;
    matches.reserve(NUM_MAX_OF_MATCHES);
    for (int p = 0, t = 0; t + P.size() - p <= T.size(); ) {
        for (; P[p] == T[t] && p < P.size(); ++p, ++t);
        if (p == P.size()) {
            ++numMatches;
            if (numMatches <= matches.capacity()) {
                matches.push_back(t - P.size());
            }
        }
        if(0 == p) {
            ++t;
        }
        else {
            p = sp[p - 1];
        }
    }

    return std::make_pair(numMatches, matches);
}

int main() {
    string P, T;
    std::ifstream in{"strmatch.in"};
    std::ofstream out{"strmatch.out"};

    in >> P >> T;
    const auto& x = strMatch(P, T);

    out << x.first << '\n';
    std::copy(x.second.begin(), x.second.end(), std::ostream_iterator<int>{out, " "});
    out << '\n';

    return 0;
}