Cod sursa(job #2451860)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 28 august 2019 14:39:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <iostream>
#include <string.h>
using namespace std;

ifstream fin{"strmatch.in"};
ofstream fout{"strmatch.out"};


size_t sol[1001];
size_t k{0};

char A[2000002];
char B[2000002];
size_t prefix[2000002];


int main()
{
   ios_base::sync_with_stdio(false);

   fin.getline(A, 2000002, '\n');
   fin.getline(B, 2000002, '\n');


   size_t len_a = strlen(A);
   size_t len_b = strlen(B);


    for(size_t j = 0, i = 1; i < len_a;)
    {
       if(*(A + i) == *(A + j))
       {
           prefix[i] = j + 1;
           ++i;
           ++j;
       }
       else if(j != 0) j = prefix[j - 1];
       else prefix[i++] = 0;

    }

    for(size_t j = 0, i = 0; i < len_b;)
    {
        if(A[j] == B[i])
        {
           ++i;
           ++j;

        } else if(j != 0) j = prefix[j - 1];
        else ++i;

        if(j == len_a ) {
            k++;

            if(k <= 1000) sol[k] = i - j;

        }
    }

    fout << k << "\n";

    if(k > 1000) k = 1000;

    for(size_t i = 1; i <= k; ++i) fout << sol[i] << " ";
}