Cod sursa(job #3000559)

Utilizator TanasaStefanTanasa Stefan TanasaStefan Data 12 martie 2023 16:19:10
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <cstring>
#include <iostream>

using namespace std;

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

int n , m , l , v[2000005] , p[2000005] , q , cnt = 0, k;

char a[2000005] , b[2000005];

int main()
{
    f >> (a + 1);
    f >> (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;
}