Найти диапазоны в массиве

Question

Я пытался найти оптимальное решение следующей (интересной?) Проблемы, которая возникла на работе: в конце концов я согласился на достаточно хорошее решение, но я хотел бы знать, есть ли лучшее.

Пусть a ₁ ... a _n будет массивом строк.

Пусть s ₁ ... s _k - неупорядоченный список строк, все они также являются членами массива.

Задача состоит в том, чтобы найти минимальный набор элементов диапазонов индексов s cover в a.

Так, например, если a = ["x", "y", "a", "f", "c"] и s = {"c", "y", "f"},ответ будет (1; 1), (3; 4), при условии, что массив проиндексирован с нуля.

a обычно довольно большой (сотни тысяч элементов), тогда как sотносительно мала, обычно длина (с)

Итак, вопрос в том, можете ли вы найти эффективный по времени алгоритм для этой проблемы?(Эффективность пространства не имеет значения в разумных пределах.)

Просто быстрое, но важное обновление: мне нужно выполнить эту операцию с различными значениями s, но одинаковыми a.Так что предварительные вычисления, основанные на a, разрешены, это действительно единственный способ.

Answer 1

Создайте хеш-таблицу H(a) для отображения элемента в индекс: a _x ->x в O(n) времени и пространстве.Затем найдите каждый s _y в H(a) (в среднем за O(1) времени в общей сложности O(k) для s) и отследите диапазоны.Для этого вы можете использовать массив pair(min_index, max_index), отсортированный по min_index, и выполнить бинарный поиск, чтобы найти диапазон или место, где вы должны вставить новый диапазон из 1 элемента.* время и O( n + nb_ranges ) пространство.

Answer 2

Это то, что вы хотите, написано на python:

def flattened(indexes):
    s, rest = indexes[0], indexes[1:]
    result = (s, s)
    for e in rest:
        if e == result[1] + 1:
            result = (result[0], e)
        else:
            yield result
            result = (e, e)
    yield result

a = ["x", "y", "a", "f", "c"]
s = ["c", "y", "f"]

# Create lookup table of ai to index in a
src_indexes = dict((key, i) for i, key in enumerate(a))

# Create sorted list of all indexes into a
raw_dst_indexes = sorted(src_indexes[key] for key in s)

# Convert sorted list of indexes into an array of ranges
dst_indexes = [r for r in flattened(raw_dst_indexes)]

print dst_indexes

Answer 3

Я думаю, что вы можете бросить элементы S в набор или хеш-таблицу, что угодно с почти O (1), чтобы проверить членство. Затем просто проведите линейное сканирование на A с флагом, чтобы определить, покрываете ли вы в настоящее время элементы в S, и начальную позицию этого покрытия. Должно быть O (n + k).