Cod sursa(job #3000708)

Utilizator livliviLivia Magureanu livlivi Data 12 martie 2023 19:15:05
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main(){
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    string a, b; in >> a >> b;

    int k = 0;
    vector<int> pi(a.size());
    for (int i = 1; i < a.size(); i++) {
        while (k > 0 && a[k] != a[i]) {
            k = pi[k - 1];
        }
        if (a[k] == a[i]) { k++; }
        pi[i] = k;
    }

    k = 0;
    vector<int> pi_b(b.size());
    // !! atentie !! aici i incepe de la 0
    for (int i = 0; i < b.size(); i++) {
        while (k > 0 && a[k] != b[i]) {
            k = pi_b[k - 1];
        }
        if (a[k] == b[i]) { k++; }
        pi_b[i] = k;
    }

    int ans = 0;
    for (int i = 0; i < b.size(); i++) {
        if (pi_b[i] == a.size()) {
            ans++;
        }
    }

    out << ans << "\n";
    ans = 0;
    for (int i = 0; i < b.size() && ans < 1000; i++) {
        if (pi_b[i] == a.size()) {
            ans++;
            out << i - a.size() + 1 << " ";
        }
    }
    out << "\n";

    return 0;
}