Задача об алгоритме строки, дп, графа или другого

Question

проблема следующая.

1. о "Ницце"

   1) "ab" - это хорошо

   2) A это хорошо => "a" + A + "b" это хорошо

   3) А и В хороши => А + В хороши

2. о "~"

   1) "ab" ~ "ab"

   2) A ~ B => "a" + A + "b" ~ "a" + B + "b"

   3) A ~ B и C ~ D => A + C ~ B + D и A + C ~ D + B

теперь существует не более 1000 строк 'a' и 'b', образующих множество S, найдите наибольшее подмножество S, в котором каждый элемент должен быть хорошим, и ни одна из пары (A, B) не содержит A ~ B. Выведите количество элементов.

Есть другие проблемы, которые я видел раньше: A + B + C + D ~ A + C + B + D ~ B + D + A + C, но A + B + C + D ~ B + D + A + C не выполняется.

Две трудности для меня:

1. как проверить, есть ли S1 ~ S2
2. если я знаю каждую пару "~", как я могу найти мощность

подробнее: https://www.spoj.pl/problems/ABWORDS/

Answer 1

Правила построения хорошего слова подразумевают, что каждое хорошее слово начинается с «а» и заканчивается «б».Следовательно, существует уникальное (вплоть до упорядочения - правило 3) разложение красивого слова на красивые подслов: найти все «ab», а затем попытаться расширить их, используя правило 2, и упорядочить их, используя правило 3. Мыможет выразить это разложение через дерево (n ветвей для повторного применения правила 3).

В контексте дерева отношение "~" просто выражает изоморфные деревья, я думаю (где порядок ветвления не имеет значения).

РЕДАКТИРОВАТЬ : как указано, порядок ветвления имеет значение.

Я попытаюсь решить проблему, как указано в исходной ссылке(2 определения «nice» не совпадают).

Во-первых, сходство между двумя словами X и Y с использованием DP.

Определите f(a, b, n) как функциюэто означает, что X[a..a+2n-1] похоже на Y[b..b+2n-1] и что оба подслова хороши.

f(a, b, 0) = 1.

для n> 0,

f(a, b, n) = f1(a, b, n) or f2(a, b, n) or f3(a, b, n)
f1(a, b, n) = x[a] == y[b] == 'a' and x[a+2n-1] == y[b+2n-1] == 'b' and f(a+1, b+1, n-1)
f2(a, b, n) = any(1 <= k < n) f(a, b, k) and f(a+2k, b+2k, n-k)
f3(a, b, n) = any(1 <= k < n) f(a, b+2(n-k), k) and f(a+2k, b, n-k)

Я думаю, что это O (n ^4) (Ург).

Для второй части, если вы представляете слова в виде графа с представлением реберЧто касается отношения сходства, я думаю, вы пытаетесь найти максимально независимый набор.Если это так, удачи!В общем случае это NP-сложный (то есть, нет лучшего решения, чем пробовать все комбинации), и я не вижу каких-либо свойств, облегчающих это: (

EDITED Чтобы определить сходство автоматически, проверьте правильность. Это довольно легко.

EDITED еще раз из-за моей глупости.