Cod sursa(job #2471511)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 11 octombrie 2019 07:11:53
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

size_t lcsp[2000001];       //cel mai lung sufix care e si prefix

size_t sol[1001];

char a[2000001];
char b[2000001];

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

    fin.getline(a, 2000000, '\n');
    fin.getline(b, 2000000, '\n');


    for(size_t k = 0, i = 1; a[i] != '\0'; ++i)
    {
        while(k && a[k] != a[i]) k = lcsp[k - 1];

        if(a[i] == a[k]) ++k;

        lcsp[i] = k;
    }

    size_t gasite = 0, n = strlen(a);

    for(size_t k = 0, i = 1; b[i] != '0'; ++i)
    {
        while(k && a[k] != b[i]) k = lcsp[k - 1];

        if(a[k] == b[i]) ++k;

        if(k == n)
        {
            sol[++gasite] = i - k + 1;

            if(gasite == 1000) break;
        }
    }

    fout << gasite << '\n';

    for(size_t i = 1; i <= gasite; ++i) fout << sol[i] << ' ';
}