Cod sursa(job #2807272)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 23 noiembrie 2021 16:55:31
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;
const int NMAX = 2000000;

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

char s[2 * NMAX], aux[NMAX], ch;
int z[2 * NMAX];
int pos[1000];

void initZ(char s[], int z[])
{
    int len = strlen(s), l = 0, r = 0;
    z[0] = 0;
    for (int i = 1; i < len; i++)
    {
        if (r <= i)
            z[i] = 0;
        else
            z[i] = min(z[i - l], r - i + 1);
        while (i + z[i] < len && s[z[i]] == s[i + z[i]])
            z[i]++;
        if (r < i + z[i] - 1)
        {
            l = i;
            r = i + z[i];
        }
    }
}


int main()
{
    int nrap, j, len1, len2, i;
    fin >> aux;
    len1 = strlen(aux);
    for (j = 0; j < len1; j++)
        s[j] = aux[j];
    ch = fin.get();
    fin >> aux;
    len2 = strlen(aux);
    for (i = 0, j = len1; j < len1 + len2; j++, i++)
        s[j] = aux[i];

    initZ(s, z);
    nrap = 0;
    for (j = len1; j < len2 + len1; j++)
        if (z[j] >= len1)
        {
            if (nrap < 1000)
                pos[nrap] = j - len1;
            nrap++;
        }
    fout << nrap << '\n';
    for (j = 0; j < min(nrap, 1000); j++)
        fout << pos[j] << " ";
    return 0;
}