Учитывая массив длинных строк, как эффективно проверить заданные пары подстрок (заданных строк), если они отличаются максимум одним символом?

Question

Любая пара подстрок имеет одинаковую длину.Необходимо проверить много пар подстрок, поэтому наивное сравнение недостаточно эффективно, но я не могу придумать какой-либо предварительной обработки массива строк, которая бы ускорила процесс сравнения.Заранее спасибо!

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

массив длинных строк:

str = {"aaaaa", "aaabbcc", "abcdefgh"...}

проверяемых пар подстрок:

pairs = {(str[0][0..1],str[1][1..2]), (str[0][1..4],str[2][3..6]), (str[1][2..4], str[2][0..2])...}

пары подстрок, которые нужно проверить (подставить в):

pairs = {("aa","aa"), ("aaaa","defg"), ("abb","abc")...}

конечный результат:

result = {true, false, true}

Наивное сравнение приведет к времени выполнения O(|pairs|*max(|str[i]|)),и я хотел бы улучшить это.

Answer 1

(Перекрестная публикация моего ответа от Quora здесь).

ИМО, вопрос не был сформулирован очень четко, но я думаю, что он задает следующий вопрос: нам дан набор строк S [1], S [2],…, S [N] и набор запросов, каждый из которых принимает форму (i1, j1, i2, j2, L).Ответ на такой запрос - «да», если строки длины L, начинающиеся в позиции j1 в S [i1] и в позиции j2 в S [i2], отличаются изменением не более чем на один символ, в противном случае - «нет».Сумма L-значений по всем таким запросам может быть намного больше, чем общая длина строк.

В этом случае мы можем разработать эффективный алгоритм, используя следующее наблюдение: если S и T - строкидлины L, то выражение «S и T различаются изменением не более одного символа» эквивалентно «LCP (S, T) + LCP (R (S), R (T))> = L-1»где R обозначает обращение строки, а LCP - длину самого длинного общего префикса двух строк.

Таким образом, для эффективного ответа на запросы нам нужно только предварительно обработать строки S [1],…, S [N] и R (S [1]),…, R (S [N]), поэтому запросы с самым длинным общим префиксом выполняются быстро.Это можно сделать путем объединения S [1],…, S [N], чтобы получить одну строку S, и построения массива суффиксов и массива самых длинных общих префиксов из S,затем делая то же самое для обратного S. Определение LCP двух подстрок исходных строк тогда эквивалентно определению LCP двух подстрок S (*), что эквивалентно запросу минимального диапазона в массиве LCP,на который можно эффективно ответить путем предварительной обработки.Аналогичное утверждение справедливо для обращений исходных строк и обращения к S.

(*) Технически, LCP в объединенной строке S может выходить за границы исходных строк.Однако это произойдет только в том случае, если подстроки запроса фактически идентичны, поэтому это будет означать, что мы ответим «да» в тех случаях, когда ответ «да» в любом случае.

Answer 2

Вы можете попробовать использовать деревья суффиксов: https://en.wikipedia.org/wiki/Suffix_tree

Сначала преобразуйте все строки в деревья суффиксов.Это можно сделать за время O (n), где n - длина строки.

Затем вы можете рекурсивно попробовать все возможные строки, чтобы увидеть, являются ли они подстрокой хотя бы из 2 строк.

Вы начинаете с набора, включающего указатели на корень всех деревьев.Это отражает то, что '' является подстрокой всех строк.Затем для каждого символа найдите подмножество деревьев, у которых есть соответствующий дочерний элемент.Например, для «а» найдите все указатели, которые в наборе, у которых есть ребенок, помечены «а».Для любого непустого набора вы нашли новую общую подстроку и рекурсивно проверяете более длинную.

Если вы хотите учесть одно различие, то рекурсивный вызов также должен включать количество различий до сих пор.Если это 1, то разрешены только совпадающие дочерние элементы.Если это 0, то вы также можете выполнить рекурсию для каждой пары (c1, c2), где одна строка имеет дочерний элемент c1, а некоторые другие имеют дочерний элемент c2.* m + m * k * m * l) где n - максимальная длина строки, а m - их количество, k - количество найденных подстрок и l - максимальная длина найденной подстроки.