Cod sursa(job #3040204)

Utilizator stefan05Vasilache Stefan stefan05 Data 29 martie 2023 15:13:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
///infoarena Potrivirea sirurilor
#include <fstream>
#include <vector>

#define SMAX 2000005

using namespace std;

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

char a[SMAX], b[SMAX];
int lps[SMAX];
int k;
vector<int> rez;
int i;

int main()
{
    fin >>a>>b;

    k = -1; lps[0] = 0;
    for (i = 1; a[i]; ++i)
    {
        while (k > 0 && a[k+1] != a[i]) k = lps[k];
        if (a[k+1] == a[i]) k++;
        lps[i] = k;
    }

    k = -1;
    for (i = 0; b[i]; ++i)
    {
        while (k > 0 && a[k+1] != b[i]) k = lps[k];
        if (a[k+1] == b[i]) k++;
        if (!a[k+1])
        {
            rez.push_back(i-k);
            k = lps[k];
        }
    }

    fout <<min((int)rez.size(), 1000)<<'\n';
    for (i = 0; i < min((int)rez.size(), 1000); ++i)
        fout <<rez[i]<<' ';
    fout <<'\n';
    fout.close();
    return 0;
}