Cod sursa(job #3000530)

Utilizator TanasaStefanTanasa Stefan TanasaStefan Data 12 martie 2023 16:03:20
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>
using namespace std;

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

int n , m , l , v[200005] , p[200005] , q , cnt , k;

char a[200005] , b[200005];

int main()
{
    f >> ( a +  1) >> ( b + 1 );

    n = strlen(a + 1);
    m = strlen(b + 1);

    p[1] = 0;
    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;
    }
    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)
        {
            cnt++;
            if(cnt <= 1000)
            {
                k++;
                v[k] = i - n;
            }
        }
    }

    g << cnt << '\n';

    for ( int i = 1 ; i <= k ; i++)
        {
            g << v[i] << " ";
        }

        return 0;
}