Cod sursa(job #3155784)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 9 octombrie 2023 18:02:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int max_size = 2e6 + 1;

string a, b;
int p[max_size];
vector <int> ans;

void kmp ()
{
    int n = a.size() - 1, 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 ()
{
    in >> a >> b;
    int n = a.size(), m = b.size(), rez = 0;
    a = '$' + a;
    b = '$' + b;
    kmp();
    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;
}