Cod sursa(job #2729413)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 24 martie 2021 18:10:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>

std::fstream in ("strmatch.in", std::ios::in) ;
std::fstream out ("strmatch.out", std::ios::out) ;

int main() {
    std::string A, B ;
    in >> A >> B ;
    std::string tot = A + '!' + B ;
    int i, prev ;
    std::vector<int> pi(tot.size(), 0) ;
    std::vector<int> sol ;
    for (i = 1 ; i < tot.size() && sol.size() < 1000 ; ++ i) {
        prev = pi[i - 1] ;
        while (prev && tot[prev] != tot[i]) {
            prev = pi[prev - 1] ;
        }
        prev += (tot[prev] == tot[i]) ;
        pi[i] = prev ;
        if (pi[i] == A.size()) {
            sol.push_back(i - 2 * A.size()) ;
        }
    }
    out << sol.size() << '\n' ;
    for (auto it : sol) {
        out << it << ' ' ;
    }
}