Cod sursa(job #2860679)

Utilizator CoroloHorjea Cosmin Corolo Data 2 martie 2022 22:15:23
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

int main() {
    string A, B;
    f >> A >> B;
    vector<int> ans;
    int n = B.size();

    vector<int> lps = prefix_function(A);
    int j = 0, i = 0;
    while (i < n) {
        if (B[i] == A[j]) {
            if (j == A.size() - 1) {
                ans.push_back(i - A.size() + 1);
                // cout << i - A.size() + 1;
                j = 0;
                continue;
            }
            j++;
            i++;
        } else {
            if (j > 0) {
                j = lps[j];
            } else {
                i++;
            }
        }
    }
    g << ans.size() << endl;
    for (int i : ans) {
        g << i << " ";
    }
    f.close();
    g.close();
}