Cod sursa(job #2451854)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 28 august 2019 14:04:36
Problema Potrivirea sirurilor Scor 2
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 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};

size_t prefix[2000001];
char* A{new char};
char* B{new char};

int main()
{
    fin >> A >> B;

    for(size_t j = 0, i = 1; i < strlen(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 < strlen(B);)
    {
        if(*(A + j) == *(B + i))
        {
           ++i;
           ++j;

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

        if(j == strlen(A)) sol[++k] = i - j;

        if(k == 1000) break;
    }

    fout << k << "\n";

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