Cod sursa(job #3040288)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 29 martie 2023 18:05:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int max_size = 2e6 + 1;

int p[max_size], n, m;
string a, b;

void prefix ()
{
    int q = 0;
    for (int i = 2; i <= n; i++)
    {
        while (q > 0 && a[q + 1] != a[i])
        {
            q = p[q];
        }
        if (a[q + 1] == a[i])
        {
            q++;
        }
        p[i] = q;
    }
}

int main ()
{
    a += '$';
    b += '$';
    string s;
    in >> s;
    a += s;
    in >> s;
    b += s;
    n = a.size() - 1;
    m = b.size() - 1;
    prefix();
    vector <int> ans;
    int rez = 0;
    int q = 0;
    for (int i = 1; i <= m; i++)
    {
        while (q > 0 && a[q + 1] != b[i])
        {
            q = p[q];
        }
        if (a[q + 1] == b[i])
        {
            q++;
        }
        if (q == n)
        {
            rez++;
            if (rez <= 1000)
            {
                ans.push_back(i - n);
            }
        }
    }
    out << rez << '\n';
    for (auto f : ans)
    {
        out << f << " ";
    }
    in.close();
    out.close();
    return 0;
}