Cod sursa(job #2883504)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 1 aprilie 2022 16:06:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i, j, n, m;
vector <int> pi, out;
char a[2000002], b[2000002];
void prefix ()
{
    int k = 0;
    pi.resize(n+1);
    pi[1] = 0;
    for (i = 2; i <= n; i++)
    {
        while (k > 0 && a[k+1] != a[i])
            k = pi[k];
        if (a[k+1] == a[i])
            k++;
        pi[i] = k;
    }
}
int main()
{
    fin >> (a+1) >> (b+1);
    a[0] = ' ';
    b[0] = ' ';
    n = strlen(a)-1;
    m = strlen(b)-1;
    prefix();
    int q = 0;
    for (i = 1; i <= m; i++)
    {
        while (q > 0 && a[q+1] != b[i])
            q = pi[q];
        if (a[q+1] == b[i])
            q++;
        if (q == n && out.size() <= 1000)
            out.push_back(i-n);
    }
    fout << out.size() << "\n";
    for (i = 0; i < min((int) out.size(), 1000); i++)
        fout << out[i] << " ";
    return 0;
}