Cod sursa(job #2596069)

Utilizator k2e0e0w3qDumitrescu Gheorghe k2e0e0w3q Data 9 aprilie 2020 11:08:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <string>
#include <set>
#include <iterator>
#include <algorithm>

constexpr auto NMAX = 1000;


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

int n, m;
std::string text, pattern;
std::vector <int> lps;
std::set <int> Store;


inline void Compute_LPS () {
    int len = 0, i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len])
            ++ len, lps[i] = len, ++ i;
        else {
            if (len) len = lps[len - 1];
            else lps[i] = 0, ++ i;
        }
    }
}

inline void KMP_Search () {
    int i = 0, j = 0;
    n = (int)text.size (), m = (int)pattern.size ();
    lps.assign (m, 0);
    if (n < m) goto end;

    Compute_LPS ();
    while (i < n) {
        if (text[i] == pattern[j])
            ++ i, ++ j;
        if (j == m && n > NMAX) {
            if ((int)Store.size () < NMAX)
                Store.insert (i - j), j = lps[j - 1];
            else goto end;
        }
        else if (j == m && n <= NMAX)
            Store.insert (i - j), j = lps[j - 1];
        else if (i < n && text[i] != pattern[j]) {
            if (j) j = lps[j - 1];
            else ++ i;
        }
    }
    end : ;
}


int main () {
    fin >> pattern >> text;
    KMP_Search ();
    fout << Store.size () << "\n";
    while (Store.size()>NMAX)
        Store.erase(Store.begin());
    std::copy (Store.begin (), Store.end (), std::ostream_iterator <int> (fout, " "));

    fin.close (), fout.close ();
    return 0;
}