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

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

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

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

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

Ответ 1

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

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

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

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

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

Ответ 2

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

Нам присваивается строка 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, чтобы покрыть все буквы в s.

Ответ 3

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

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

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

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