Cod sursa(job #3138364)

Utilizator SSKMFSS KMF SSKMF Data 19 iunie 2023 10:01:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

char sir[2][2000001];
int prefixe[2000000];

int main ()
{
    cin >> sir[0] >> sir[1];

    for (int indice = 1 , lungime_prefix = 0 ; sir[0][indice] ;)
        if (sir[0][indice] == sir[0][lungime_prefix]) {
            prefixe[indice] = ++lungime_prefix;
            indice++;
        }
        else
            if (lungime_prefix > 0)
                lungime_prefix = prefixe[lungime_prefix - 1];
            else
                prefixe[indice++] = 0;

    int aparitii = 0 , indici[1000];
    for (int indice_1 = 0 , indice_2 = 0 ; sir[1][indice_2] ;)
    {
        if (sir[0][indice_1] == sir[1][indice_2])
        {
            indice_1++ , indice_2++;

            if (!sir[0][indice_1]) {
                if (aparitii < 1000)
                    indici[aparitii++] = indice_2 - indice_1;
                else
                    aparitii++;

                indice_1 = prefixe[indice_1 - 1];
            }
        }
        else
            if (indice_1)
                indice_1 = prefixe[indice_1 - 1];
            else
                indice_2++;
    }

    cout << aparitii << '\n';
    for (int indice = 0 ; indice < aparitii ; indice++)
        cout << indici[indice] << ' ';
           
    cout.close(); cin.close();
    return 0;
}