Cod sursa(job #2991295)

Utilizator RobertlelRobert Robertlel Data 9 martie 2023 11:22:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

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

char a[2000005] , b[2000005];

int main()
{
    f >> (a + 1);
    f >> (b + 1);
    n = strlen (a + 1);
    m = strlen (b + 1);
    q = 0;
    p[1] = 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 << k << '\n';;
    for (int i = 1 ; i <= k ; i++)
        g << v[i] <<" " ;
    return 0;
}