Cod sursa(job #2471515)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 11 octombrie 2019 07:35:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 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, 2000001, '\n');
    fin.getline(b, 2000001, '\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 = 0; b[i] != '\0'; ++i)
    {
        while(k && a[k] != b[i]) k = lcsp[k - 1];

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

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

        }
    }

    fout << gasite << '\n';

    if(gasite > 1000) gasite = 1000;

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