Conversation with Merlin [email protected] · Fri Dec 08 2023

Czesc. Ten kod sprawdza czy podany ciag znakow na poczatku mozna poskladac z wyrazow podanych pozniej. Mozesz mi wytlumaczyc algorytm? #include<bits/stdc++.h>

// Solution with no hashing // optimalization: map with single letters // binary search on all letters // string comparison when hashes equal // asserts and sync off

using namespace std;

int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); string txt; cin >> txt;

const int size = txt.size();
assert(size <= 100000 && size > 0);

set<char> txtLetters;
for (auto& c : txt)
{
    assert('A' <= c && c <= 'Z');
    txtLetters.insert(c);
}

int n{};
cin >> n;
vector<string> words(n);
set<char> wordsLetters;
for (auto& s : words)
{
    cin >> s;

    for (auto& c : s)
        assert('A' <= c && c <= 'Z');

    assert((int)s.size() <= size && !s.empty());

    if ((int)s.size() == 1)
        wordsLetters.insert(s.front());
}

sort(words.begin(), words.end());
for (int i{1}; i<n; ++i)
    assert(words[i] != words[i-1]);

// condition for one-letter strings
if (txtLetters.size() == wordsLetters.size())
{
    for (char c : txt)
        cout << c << ' ';
    cout << endl;
    return 0;
}

vector<int> dp(size + 1, -1);
dp[0] = -2;

for (int i{}; i<size; ++i)
{
    if (dp[i] == -1)
        continue;

    int index = 0;

    auto it1 = words.begin();
    auto it2 = words.end();
    while(it1 != it2)
    {

        auto newIt1 = lower_bound(it1, it2, txt[i + index], [&index](const string& s, char c)
        {
            if (index >= (int)s.size()) return false;
            return s[index] < c;
        });

        if (newIt1 == it2 || (*newIt1)[index] != txt[i + index])
            break;

        auto newIt2 = lower_bound(newIt1, it2, txt[i + index] + 1, [&index](const string& s, char c)
        {
            if (index >= (int)s.size()) return false;
            return s[index] < c;
        });

        it1 = newIt1;
        it2 = newIt2;

        auto j = distance(words.begin(), it1);

        int sizeV = words[j].size();

        if (index + 1 == sizeV)
        {
            it1++;

            dp[i + sizeV] = j;
        }
        else
        {
            index++;
        }
    }
}

if (dp.back() == -1)
{
    cout << "NIE\n";
}
else
{
    vector<string> res;
    int i = txt.size();
    while (i > 0)
    {
        int j = dp[i];
        res.push_back(words[j]);
        i -= words[j].size();
    }
    assert(i == 0);
    reverse(res.begin(), res.end());
    for (auto& s : res)
        cout << s << ' ';
    cout << '\n';
}

}

Witaj! Powyższy kod jest programem w C++, który bada, czy określony ciąg znaków może być złożony z listy słów podanych na wejściu. Przyjrzyjmy się temu algorytmowi krok po kroku:

  1. Inicjalizacja I/O:

    • Wyłączenie synchronizacji strumieni C i C++ dla szybszego I/O.
    • Przyspieszenie operacji wczytywania danych (cin.tie(nullptr)).

  2. Wczytanie ciągu znaków txt oraz sprawdzenie poprawności danych wejściowych:

    • Długość ciągu nie przekracza 100000 znaków.
    • Wszystkie znaki w ciągu są wielkimi literami alfabetu angielskiego (A-Z).

  3. Stworzenie zbioru znaków, które występują w txt.

  4. Wczytanie liczby słów n oraz samych słów do wektora words.

    • Sprawdzenie poprawności słów (wszystkie litery są wielkimi literami alfabetu angielskiego i długość słowa jest nie większa niż długość txt).
    • Dodanie wszystkich unikatowych liter, które są jednoznakowymi słowami, do zbioru wordsLetters.

  5. Sortowanie wektora words i upewnienie się, że słowa są unikatowe.

  6. Sprawdzenie szczególnego przypadku: jeśli wszystkie litery z txt są unikatowe i odpowiadają jednoznakowym słowom, wypisuje je i kończy działanie algorytmu.

  7. Inicjalizacja wektora dp do przechowywania indeksów:

    • Wartości są inicjalizowane na -1, a dp[0] na -2, co jest potrzebne do znalezienia rozwiązania.

  8. Rozpoczęcie głównego algorytmu dynamicznego:

    • Iteracja przez cały ciąg txt, poszukując słów, od indeksu i.
    • Wyszukiwanie binarne dla każdej litery ciągu, aby znaleźć pierwsze i ostatnie słowo w words zaczynające się na tę literę.
    • Uaktualnienie zmiennych it1 i it2 w celu ograniczenia przeszukiwania.
    • Sprawdzenie, czy obecne słowo pasuje do fragmentu txt zaczynając od i.
    • Jeśli doszliśmy do końca słowa (sizeV), aktualizujemy dp[i + sizeV] z obecnym indeksem j.
    • Kontynuacja dopasowywania kolejnych liter słowa.
    • Jeśli nie znajdzie się żadne pasujące słowo, iteracja jest kontynuowana z następnego indeksu i.

  9. Po przejściu przez txt, jeśli dp.back() (ostatni element wektora dp) wynosi -1, nie udało się złożyć ciągu z podanych słów – wypisuje "NIE".

  10. Jeżeli znaleziono rozwiązanie:

    • Przechodzi się od końca wektora dp zbierając słowa, które tworzą odpowiednie fragmenty ciągu txt.
    • Odtwarza ostateczną sekwencję słów odwracając wektor wyników.
    • Wypisuje wynikowe słowa.

Algorytm ten korzysta z programowania dynamicznego, gdzie dp przechowuje indeksy słów z words, które mogą być użyte do zbudowania txt. To pozwala na optymalne rozwiązanie problemu poprzez unikanie wielokrotnego przeanalizowania tych samych podsekwencji. Wyszukiwanie binarne w połączeniu z programowaniem dynamicznym i sortowaniem sprawia, że algorytm jest wydajny nawet dla dużych danych wejściowych.