H100025. 单词拆分 ACM 版

import sys

data = sys.stdin.buffer.read().split()
if not data:
    raise SystemExit

text = data[0].decode()
word_count = int(data[1])
dictionary = {token.decode() for token in data[2 : 2 + word_count]}
max_word_length = max(map(len, dictionary), default=0)

possible = [False] * (len(text) + 1)
possible[0] = True  # 空前缀不需要任何单词，可以被拆分。
for end in range(1, len(text) + 1):
    first_start = max(0, end - max_word_length)
    for start in range(first_start, end):
        # 前缀可拆分，且最后一段是词典单词时，当前前缀可拆分。
        if possible[start] and text[start:end] in dictionary:
            possible[end] = True
            break

print("YES" if possible[len(text)] else "NO")