b.py

# https://contest.yandex.ru/contest/26133/run-report/154321215/
#
# -- Принцип работы --
#
# Функция `can_word_split()` определяет возможность разбиения строки на слова из заданного набора.
# Для эффективного поиска совпадений с подстроками, все слова предварительно добавляются в префиксное
# дерево, методы для работы с которым реализованы в классе `Trie`. Для хранения ребер, инцидентных
# дочерним узлам, в классе `TrieNode`, представляющем узел префиксного дерева, используется словарь.
#
# Метод `Trie.find_word()` проверяет заданную строку, начиная с некоторой позиции, на совпадение со
# словами, находящимися в префиксном дереве. Совпадений может оказаться несколько, поэтому функция
# возвращает итерируемый объект, перечисляющий конечные позиции совпадений слов со строкой.
#
# В методе `Trie.can_word_split()` поиск возможных разбиений строки осуществляется с использованием
# динамического программирования. Значение флага существования разбиения для каждого префикса исходной
# строки сохраняется в список `results` под индексом, равным длине префикса. Для строки нулевой длины
# мы по определению считаем, что разбиение возможно.
#
# Далее мы проверяем в цикле все возможные позиции заданной строки. Если для префикса, находящегося
# непосредственно перед текущей позицией, разбиение на слова существует, то мы выполняем проверку
# на совпадения с содержимым префиксного дерева для подстроки, начинающейся с текущей позиции. Если
# совпадения были найдены, то мы сохраняем их в массив результатов и используем при дальнейших
# проверках. Таким образом, после прохода цикла по всем позициям флаг существования разбиения для
# исходной строки будет сохранен в последнем элементе массива результатов.
#
# -- Доказательство корректности --
#
# Для доказательства корректности алгоритма поиска разбиений воспользуемся методом математической
# индукции.
#
# * Для префикса исходной строки `s` нулевой длины функция `Trie.can_word_split()` корректно сохраняет
#   в элемент списка `results[0]` значение `True`.
# * Предположим, что алгоритм работает правильно для каждого префикса исходной строки `s` длины меньшей
#   некоторого значения `t`. Функция запишет в элемент списка `results[t]` значение `True` тогда и
#   только тогда, когда в префиксном дереве существует слово `wᵢ`, с длиной `|wᵢ|`, которое совпадает
#   с подстрокой `s[t - |wᵢ|, t)`, и при этом в элементе `results[t - |wᵢ|]` находится значение `True`.
#   Но из сделанного ранее предположения вытекает, что в этом случае существует разбиение на слова
#   для префикса `s[0, t - |wᵢ|)`. Таким образом, разбиение префикса `s[0, t)` также существует, и,
#   следовательно, для длины префикса `t` алгоритм тоже отработает корректно.
#
# Таким образом, существование разбиения на слова корректно определяется для всех префиксов исходной
# строки `s`, включая эту строку целиком.
#
# -- Временная сложность --
#
# Временная сложность добавления набора слов `w` в префиксное дерево составляет `O(Σ|wᵢ|)`. Временная
# сложность поиска разбиений строки `s` определяется количеством сравнений символов, выполняемых в
# цикле для каждой позиции строки, и зависит от исходных данных. Например, если какое-то слово из
# набора `w` является префиксом другого, и оба этих слова содержатся в строке `s`, то алгоритм должен
# будет проверить возможные варианты разбиения, содержащие оба этих слова. На практике, если набор
# `w` составлен из слов какого-то естественного языка, то среднее количество совпадений слов из `w`
# с подстроками `s` будет значительно меньше общего количества слов в `w`. Поэтому временную сложность
# определения возможности представления строки `s` как комбинации слов из префиксного дерева можно
# оценить как `O(|s|)`. Таким образом, суммарная вычислительная сложность алгоритма составляет
# `O(|s| + Σ|wᵢ|)`.
#
# -- Пространственная сложность --
#
# Пространственная сложность добавления набора слов `w` в префиксное дерево в среднем составляет
# `O(Σ|wᵢ|)`. Помимо этого, промежуточные результаты поиска возможных разбиений строки `s` сохраняются
# в массив длиной `O(|s|)`. Таким образом, итоговая пространственная сложность алгоритма составляет
# `O(|s| + Σ|wᵢ|)`.

from __future__ import annotations

import sys
from collections.abc import Iterable


def can_word_split(s: str, words: Iterable[str]) -> bool:
    trie = Trie(words=words)
    return trie.can_word_split(s)


class TrieNode:
    is_word_end: bool
    children: dict[str, TrieNode]

    __slots__ = (
        'is_word_end',
        'children',
    )

    def __init__(self) -> None:
        self.is_word_end = False
        self.children = {}


class Trie:
    root: TrieNode

    __slots__ = (
        'root',
    )

    def __init__(self, *, words: Iterable[str] | None = None) -> None:
        self.root = TrieNode()

        if words is not None:
            self.add_words(words)

    def add_words(self, words: Iterable[str]) -> None:
        for word in words:
            self.add_word(word)

    def add_word(self, word: str) -> None:
        node = self.root

        for char in word:
            child_node = node.children.get(char)

            if child_node is None:
                node.children[char] = child_node = TrieNode()

            node = child_node

        node.is_word_end = True

    def find_word(self, s: str, start_pos: int = 0) -> Iterable[int]:
        node = self.root
        s_length = len(s)
        pos = start_pos

        while True:
            if node.is_word_end:
                yield pos

            if pos >= s_length:
                break

            char = s[pos]
            child_node = node.children.get(char)

            if child_node is None:
                break

            node = child_node
            pos += 1

    def can_word_split(self, s: str) -> bool:
        s_length = len(s)
        results = [False] * (s_length + 1)
        results[0] = True

        for start_pos in range(s_length):
            if not results[start_pos]:
                continue

            for end_pos in self.find_word(s, start_pos):
                results[end_pos] = True

        return results[s_length]


def read_words(count: int) -> Iterable[str]:
    for i in range(count):
        yield sys.stdin.readline().strip()


def main() -> None:
    s = sys.stdin.readline().strip()
    words_count = int(input().strip())
    words = read_words(words_count)

    print('YES' if can_word_split(s, words) else 'NO')


if __name__ == '__main__':
    main()