Cod sursa(job #2883751)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 1 aprilie 2022 19:32:50
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <vector>

using namespace std;

int kmp[2000002];

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

}