Cod sursa(job #2730114)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 25 martie 2021 19:44:08
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 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, left(0), rightMost(0) ;
    std::vector<int> z(tot.size()) ;
    std::vector<int> sol ;
    for (i = 1 ; i < tot.size() ; ++ i) {
      if (i <= rightMost) {
        z[i] = std::min(rightMost - i + 1, z[i - 1]);
      }
      while (i + z[i] < tot.size() && tot[z[i]] == tot[z[i] + i]) {
        z[i] ++ ;
      }
      if (i + z[i] - 1 > rightMost) {
        left = i ;
        rightMost = i + z[i] - 1 ;
      }
      if (z[i] == A.size()) {
        sol.push_back(i - A.size() - 1) ;
      }
    }
    out << sol.size() << '\n' ;
    if (sol.size() > 1000) {
      sol.erase(sol.begin() + 1000, sol.end()) ;
    }
    for (auto it : sol) {
      out << it << ' ' ;
    }
}