Cod sursa(job #2976161)

Utilizator Constantin.Dragancea Constantin Constantin. Data 8 februarie 2023 15:14:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

vector <int> ComputePI(string s){
    int n = s.size();

    vector <int> pi(n);
    pi[0] = 0;

    for (int i = 1; i < n; i++){
        pi[i] = 0;
        int j = pi[i - 1];
        for (; j; j = pi[j - 1]){
            if (s[i] == s[j]){
                pi[i] = j + 1;
                break;
            }
        }

        if (j == 0 && s[0] == s[i])
            pi[i] = 1;
    }
    return pi;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    string s, t;
    cin >> s >> t;

    auto pi = ComputePI(s + "#");

    int last = 0, ans = 0;
    int LIM = 1000;
    vector <int> sol;
    int n = s.size();
    int m = t.size();

    for (int i = 0; i < m; i++){
        int curr = 0;
        int j = last;
        for (; j; j = pi[j - 1]){
            if (t[i] == s[j]){
                curr = j + 1;
                break;
            }
        }

        if (j == 0 && s[0] == t[i])
            curr = 1;
        
        if (curr == n){
            ans++;
            if (LIM > 0){
                sol.push_back(i - n + 1);
                LIM--;
            }
        }
        last = curr;
    }

    cout << ans << '\n';
    for (int it: sol)
        cout << it << ' ';

    return 0;
}