Проверьте, может ли данная строка быть создана набором символов, вырезанных из статьи в журнале

Question

"Заметьте, что при вырезании символа из журнала символ на обратной стороне страницы также удаляется. Дайте алгоритм, чтобы определить, можно ли сгенерировать заданную строку, вставив вырезки из данного журнала. Предположим, чточто вам дана функция, которая идентифицирует персонажа и его положение на обратной стороне страницы для любой заданной позиции персонажа. "

Как я могу это сделать?

Я могу сделать несколькопервоначальное сокращение, так что если у необходимого персонажа есть только один способ быть подобранным, его сначала берут перед включением подзадачи для динамической техники, но что после этого первоначального сокращения?

Какова сложность времени и пространства

Answer 1

Как подсказывает @LiKao, это можно решить с помощью максимального потока.Чтобы построить сеть, мы создаем два «слоя» вершин: один со всеми различными символами во входной строке и один с каждой позицией на странице.Сделайте ребро со способностью 1 от персонажа до позиции, если эта позиция имеет этот символ на одной стороне.Сделайте ребра емкостью 1 от каждой позиции до приемника и сделайте ребра от источника до каждого символа с емкостью, равной кратности этого символа во входной строке.

Например, предположим, что мы ищемдля слова "FOO" на странице с четырьмя позициями:

pos    1 2 3 4
front  F C O Z
back   O O K Z

Затем мы создаем следующую сеть, игнорируя позицию 4, поскольку она не предоставляет ни одного из необходимых символов.

Теперь нам нужно только определить, существует ли поток от источника к стоку length("FOO") = 3 или более.

Answer 2

Хотя эту проблему можно сформулировать как проблему Maxflow, как показано в принятом ответе, ее проще и эффективнее сформулировать как проблему соответствия максимального количества элементов в двудольном графе.Алгоритмы Maxflow, такие как Dinic's , работают медленнее, чем алгоритмы специального случая, такие как Алгоритм Хопкрофта – Карпа .

Двудольный граф формируется путем добавления двух ребер от каждого символа данногоСтрока к вырезу, один край для каждой стороны.Затем мы запускаем Хопкрофт-Карп.В конце мы просто проверяем, равна ли мощность совпадения длине строки.

Для работающей реализации (в Scala), использующей JGraphT , см. Мой GitHub .

Я хотел бы предложить более эффективное решение для DP, поскольку в книге Скиены есть эта проблема в разделе DP, но пока что ее не найдено.

Answer 3

Вы можете использовать динамическое программирование напрямую.

Нам дана строка s с n буквами. Нам дан набор кусков P = {p_1, ..., p_k}. Каждая часть имеет одну букву в передней части p_i.f и одну в задней части p_i.b.

Обозначим через f (j, p) функцию, которая возвращает true, если возможно создать подстроку s_1 ... s_j, используя кусочки в p \ subseteq P, и false в противном случае.

Имеет место следующее повторение: f (n, P) = f (n-1, P-p_1) | f (n-1, P-p_2) | ... | f (n-1, P-p_k)

В простом английском языке выполнимость s, использующего все куски в P, зависит от выполнимости подстроки s_1 ... s_n-1, заданной на один кусочек меньше, и мы пытаемся удалить все возможные кусочки (конечно, на практике мы не делаем необходимо удалить все фрагменты по одному, нам нужно удалить только те фрагменты, для которых p_i.f == s_n || p_i.b == s_n).

Исходным условием является то, что f (1, P-p_1) = f (1, P-p2) = ... = true, при условии, что мы уже проверили a-priori (в линейном времени), что достаточно буквы в P, чтобы покрыть все буквы в с.