Cod sursa(job #2963645)

Utilizator RobertlelRobert Robertlel Data 11 ianuarie 2023 19:23:32
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

char a[200005] , b[200005];

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

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


    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++ , v[cnt] = i - n;
    }
    g << cnt << '\n';
    for (int i = 1 ; i <= cnt ; i++)
        g << v[i] << " ";
    return 0;
}