Cod sursa(job #3332970)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 10 ianuarie 2026 10:52:29
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 2e6 + 5;

string s, p;

int n, k, gap, sa[nmax], poz[nmax], tmp[nmax];

bool sufCmp (int i, int j)
{
    if (poz[i] != poz[j])
        return poz[i] < poz[j];
    i += gap;
    j += gap;
    return i < n && j < n ? poz[i] < poz[j] : i > j;
}

void buildSuffixArray ()
{
    n = s.size ();
    for (int i = 0; i < n; i++)
    {
        sa[i] = i;
        poz[i] = s[i];
    }
    for (gap = 1; ; gap *= 2)
    {
        sort (sa, sa + n, sufCmp);
        for (int i = 0; i < n - 1; i++)
            tmp[i + 1] = tmp[i] + sufCmp (sa[i], sa[i + 1]);
        for (int i = 0; i < n; i++)
            poz[sa[i]] = tmp[i];
        if (tmp[n - 1] == n - 1)
            break;
    }
}

int verif (int start, string& p)
{
    int i = 0;
    for (i = 0; i < p.size () && start + i < n; i++)
    {
        if (s[start + i] < p[i])
            return -1;
        if (s[start + i] > p[i])
            return 1;
    }
    if (i == p.size ())
        return 0;
    return -1;
}

int lowerB (string& p)
{
    int origin = -1;
    for (int bit = 1 << 20; bit; bit >>= 1)
    {
        if (origin + bit < n && verif (sa[origin + bit], p) < 0)
            origin += bit;
    }
    return origin + 1;
}

int upperB (string& p)
{
    int origin = -1;
    for (int bit = 1 << 20; bit; bit >>= 1)
    {
        int pos = origin + bit;
        if (pos < n && verif (sa[pos], p) <= 0)
            origin += bit;
    }
    return origin + 1;
}

int main ()
{
    fin >> p >> s;

    buildSuffixArray ();

    int st = lowerB (p);
    int dr = upperB (p);

    vector <int> rez;

    int total = dr - st;
    fout << total << '\n';

    int lim = min (total, 1000);

    nth_element (rez.begin (), rez.begin () + lim, rez.end ());
    rez.resize (lim);
    sort (rez.begin (), rez.end ());

    for (int i = 0; i < lim; i++)
        fout << rez[i] << ' ';
    return 0;
}