Cod sursa(job #3361025)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 18 iulie 2026 21:18:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

const int SOL_MAX_DIM = 1000;

void kmp(std::string& p, std::string& q, std::vector<int>& sol) {
    int n = p.size();
    std::vector<int> pi(n, 0);
    pi[0] = -1;
    int k = -1;

    for(int i = 1; i < n; ++ i) {
        while(k > -1 && p[i] != p[k + 1]) {
            k = pi[k];
        }
        if(p[i] == p[k + 1]) {
            k ++;
        }
        pi[i] = k;
    }

    k = -1;
    for(int i = 0; i < q.size(); ++ i) {
        while(k > -1 && q[i] != p[k + 1]) {
            k = pi[k];
        }
        if(q[i] == p[k + 1]) {
            k ++;
        }
        if(k == p.size() - 1) {
            sol.push_back(i - n + 1);
        }
    }
} 

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

    std::string p;
    std::string q;
    std::vector<int> sol;

    fin >> p >> q;
    fin.close();

    kmp(p, q, sol);

    fout << sol.size() << "\n";
    for(int i = 0; i < std::min((int)sol.size(), SOL_MAX_DIM); ++ i) {
        fout << sol[i] << " ";
    }

    fout.close();

    return 0;
}