Cod sursa(job #2164611)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 13 martie 2018 08:45:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <array>

std::array<char, 2000000U> str;
std::array<char, 2000000U> fullstr;

std::array<int, 2000000U> prefixArray;

#include <cstring>

size_t prefixSize;

void Read()
{
    std::ifstream f("strmatch.in");

    f >> str.data();
    f >> fullstr.data();

    std::cout << str.data() << ' ' << fullstr.data() << '\n';
}

void MakePrefix()
{
    size_t j = 0U, i;

    prefixArray[0] = 0U;

    for(i = 1U; str[i] != '\0'; ) {
        if(str[i] == str[j]) {
            prefixArray[i] = j + 1;

            ++i, ++j;
        }
        else if(j > 0U) {
            j = prefixArray[j - 1];
        }
        else {
            prefixArray[i] = 0;
            ++i;
        }
    }

    prefixSize = i;
}

size_t nrap = 0U;
size_t offset = 0U;

std::ofstream g("strmatch.out");

std::array<size_t, 1000U> indexArray;
size_t lastIndex = 0U;

void FindIndex()
{
    for(size_t i = 0U; fullstr[i] != '\0';) {
        if(str[offset] == fullstr[i] && offset == prefixSize - 1U) {
            ++nrap;

            if(lastIndex <= 1000U) {
                indexArray[lastIndex++] = i - offset;
            }
            else
                break;

            if(offset > 0U)
                offset = prefixArray[offset - 1U];
        }
        else if(str[offset] == fullstr[i]) {
            ++i;
            ++offset;
        }
        else if(offset > 0U) {
            offset = prefixArray[offset - 1U];
        }
        else {
            ++i;
        }
    }


    g << lastIndex << '\n';
    for(size_t k = 0U; k < lastIndex; ++k) {
        g << indexArray[k] << ' ';
    }
}

void Solve()
{
    MakePrefix();
}

int main()
{
    Read();
    Solve();
    FindIndex();
    /** std::cout << str.data() << '\n'; **/
    /** std::cout << fullstr.data() << '\n'; **/

    return 0;
}