Cod sursa(job #2420958)

Utilizator SemetgTemes George Semetg Data 13 mai 2019 17:36:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>

const std::string FILE_NAME { "strmatch" };

std::ifstream in { FILE_NAME + ".in" };
std::ofstream out { FILE_NAME + ".out" };

std::string a, b;
int solN;
std::vector<int> next(2000005), sol;

int main() {
    in >> a >> b;

    int j { 0 };
    for (int i { 1 }; i < int(a.size()); ++i) {
        while (j && a[i] != a[j])
            j = next[j - 1];

        if (a[i] == a[j])
            ++j;
        next[i] = j;
    }

    j = 0;
    for (int i { 0 }; i < int(b.size()); ++i) {
        while (j && b[i] != a[j])
            j = next[j - 1];

        if (b[i] == a[j])
            ++j;
        if (j == int(a.size())) {
            if (solN < 1000)
                sol.push_back(i - a.size() + 1);

            ++solN;
            j = next[j - 1];
        }
    }

    out << solN << '\n';
    for (const auto& i : sol)
        out << i << ' ';
}