Cod sursa(job #2985185)

Utilizator pifaDumitru Andrei Denis pifa Data 25 februarie 2023 20:09:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

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

string a, b;

int pi[4000005];

void prefix_function()
{
    int n = b.size();
    pi[0] = 0;
    for(int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while(j != 0 && b[j] != b[i])
            j = pi[j - 1];
        if(b[j] == b[i])
            j++;
        pi[i] = j;
    }
}

signed main()
{
    in >> a >> b;
    b = a + "#" + b;
    prefix_function();
    int cnt = 0;
    for(int i = a.size(); i < b.size(); i++)
    {
        if(pi[i] == a.size())
            cnt++;
    }
    out << cnt << '\n';
    int ok = 0;
    for(int i = a.size(); i < b.size() && ok < 1000; i++)
    {
        if(pi[i] == a.size())
        {
            ok++;
            int pos = i - (int)a.size() - (int)a.size();
            out << pos << ' ';
        }
    }
    return 0;
}