Cod sursa(job #2472365)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 12 octombrie 2019 11:52:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
#define NMAX 2000001
using namespace std;

char a[NMAX], b[NMAX];
size_t last[NMAX], sol[1001], gasite = 0;

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

    fin.getline(a, NMAX, '\n');
    size_t la = strlen(a);

    fin.getline(b, NMAX, '\n');
    size_t lb = strlen(b);

    for(size_t k = 0, i = 1; i < la; ++i)
    {
        while(k > 0 &&  a[i] != a[k]) k = last[k - 1];

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

        last[i] = k;
    }

    for(size_t k = 0, i = 0; i < lb; ++i)
    {
        while(k > 0 && a[k] != b[i]) k = last[k - 1];

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

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

    fout << gasite << '\n';

    if(gasite > 1000) gasite = 1000;

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