Cod sursa(job #2716544)

Utilizator andrei_culerdaCulerda Andrei andrei_culerda Data 5 martie 2021 12:22:19
Problema Potrivirea sirurilor Scor 2
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <cstring>
#include <bitset>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int N = 2000002;
const int P = 1000;
char a[N], b[N];
int pi[N];
bitset <N> c;

int main()
{
    fin >> (1 + a) >> (1 + b);
    int lung = 0, m = strlen(1 + a);
    pi[1] = 0;
    for(int i = 1; i <= m; i++)
    {
        while(lung > 0 && a[i] != a[lung + 1])
        {
            lung = pi[lung];
        }
        if(a[i] == a[lung + 1])
        {
            lung++;
        }
        pi[i] = lung;
    }

    lung = 0;
    int nr = 0;
    int n = strlen(1 + b);
    for(int i = 1; i <= n; i++)
    {
        while(lung > 0 && b[i] != a[lung + 1])
        {
            lung = pi[lung];
        }
        if(b[i] == a[lung + 1])
        {
            lung++;
        }
        if(lung == m)
        {
            c[i - m] = 1;
            nr++;
        }
    }
    fout << nr;
    nr = P;
    for(int i = 0; i < n && nr > 0; i++)
    {
        if(c[i])
        {
            fout << i << " ";
            nr--;
        }
    }
    return 0;
}