Cod sursa(job #3000566)

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

using namespace std;

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

char a[2000005] , b[2000005];

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

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;
}