Cod sursa(job #3150704)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 17 septembrie 2023 23:50:12
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
char a[2000005], b[2000005], al[2000005], bl[2000005];
int pi[2000005], n, m, j, l, nr, v[2000005];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int32_t main(int argc, char * argv[])
{
    fin >> al;
    strcpy(a + 1, al);
    n = strlen(a + 1);
    fin >> bl;
    strcpy(b + 1, bl);
     m = strlen(bl + 1);
    pi[1] = 0;
    for(int i = 2; i <= n; ++i)
    {
        while(l != 0 && a[i] != a[l + 1])
        {
            l = pi[l];
        }
        if(a[i] == a[l + 1])
        {
            l++;
        }
        pi[i] = l;
    }
    l = 0;
    for(int i = 1; i <= m; ++i)
    {
        while(l != 0 && b[i] != a[l + 1])
        {
            l = pi[l];
        }
        if(b[i] == a[l + 1])
        {
            l++;
        }
        if(l == n)
        {
            nr++;
            v[nr] = i - n + 1;
            l = pi[l];
        }
    }
    fout << nr << '\n';
    for(int i = 1; i <= min(nr, 1000); ++i)
    {
        fout << v[i] - 1 << " ";
    }
    return 0;
}