Рівняння над словами

Вам дано слово $T$ і шаблон $P$. Ви хочете перевірити, чи можна видалити деякі букви з $T$, щоб з решти символів утворити $P$. Наприклад, слово programming можна частково видалити, щоб отримати pong, program або roaming (але не map, оскільки букви повинні залишатися в тому ж порядку). Обидва слова складаються лише з малих літер англійського алфавіту.

Є лише одна складність: текст $T$ кодується системою рівнянь. У рівняннях використовуються спеціальні символи (кожен символ позначається словом з великих літер), кожен з яких кодує певне слово в алфавіті {a, ..., z}. Кожне рівняння має одну з наступних форм:

A = слово над алфавітом {a,...,z}

або

A = B + C

де A, B, C можуть бути будь-якими символами, а символ + означає конкатенацію слів. Система є:

• однозначною – для фіксованого символу A існує рівно одне рівняння з A в лівій частині;

• ациклічною – якщо ви починаєте з будь-якого символу A, робите підстановки відповідно до рівнянь, і ніколи не зможете отримати вираз, що містить A знову.

Така система завжди має єдине розв'язання. Наприклад, у системі:

• START = FIRST + SECND

• FIRST = D + E

• SECND = F + E

• D = good

• E = times

• F = bad

символ START кодує слово goodtimesbadtimes.

Маючи одне слово $P$ як шаблон, систему рівнянь і один конкретний початковий символ $S$ цієї системи, визначте, чи присутній шаблон $P$ у слові, закодованому $S$.