Cod sursa(job #2857514)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 25 februarie 2022 18:29:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

int kmp[4000004];

int main() {
    string s, t;
    in >> s >> t;
    t = " " + s + t;
    s = " " + s;
    int n = t.size() - 1;
    int k = 0;
    kmp[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        while (k > 0 && t[k + 1] != t[i])
        {
            k = kmp[k];
        }
        if (t[k + 1] == t[i]) k++;
        kmp[i] = k;
    }
    int ap = 0;
    vector<int> place;
    k = 0;
    for (int i = s.size(); i < t.size(); i++)
    {
        while (k && s[k+1] != t[i])
            k = kmp[k];
        if (s[k+1] == t[i]) k++;
        if (k == s.size() - 1){
            ap++;
            if (ap <= 1000)
                place.push_back(i);
        }
    }
    out << ap << '\n';
    for (auto a : place)
    {
        out << a - 2 * (s.size() - 1) << ' ';
    }
    return 0;
}