Cod sursa(job #3364383)

Utilizator livliviLivia Magureanu livlivi Data 2 septembrie 2026 14:32:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

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

    string pattern, text; cin >> pattern >> text;
    vector<int> match = compute_pi(pattern + "#" + text);

    int ans = 0;
    for (int i = 0; i < match.size(); i++) {
        if (match[i] == pattern.size()) {
            ans++;
        }
    }

    cout << ans << "\n";
    ans = 0;
    for (int i = 0; i < match.size() && ans < 1000; i++) {
        if (match[i] == pattern.size()) {
            ans++;
            cout << i - pattern.size() * 2 << " ";
        }
    }
    cout << "\n";

    return 0;
}