Задан набор строк и набор подстрок в виде различных массивов.Как найти правильное совпадение по одному из каждого из массивов?

Question

Пусть A = ["стек", "переполнение", "алгоритм"], B = ["gor", "tac", "flo"]. A и B - массив строк, в которых B содержит подстроки.

Гарантируется, что каждая строка в B будет подстрокой только одной строки в A, а каждая строка в A имеет только одно совпадение в B. Также учтите, что количество строк в A и B равно.

Вывод B. Так, что B [i] должна быть подстрокой A [i].

Выход для вышеприведенного примера:

B = ["tac", "flo", "gor"].

Я могу думать только о наивном подходе. У нас есть лучшее решение вышеуказанной проблемы?

Answer 1

Сделать объединение всех строк в суперструну s длины L=sum(len(i)), сохранить индексы начала строки.

Создать массив суффиксов для суперструны (LlogL)

Искать в каждой подстрокев этом массиве суффиксов (N*logL)

Получить строку, соответствующую этому индексу

---

Если подстрока не может поместиться между найденной позицией и индексом начала следующей строки, используйте другой суффикс (ситуация, подобная fax/emotion/axel и поиск axe)

Answer 2

Я предполагаю, что под наивным подходом вы подразумеваете, что каждая подстрока в B просматривает все слова в A, чтобы найти совпадение.Этот подход будет иметь сложность O (n ^ 2)

Однако вы также можете попытаться проиндексировать слова в A, используя Индекс подстроки .Построение этого индекса обычно требует времени O (n * log n).

Впоследствии вы можете использовать этот индекс для эффективного (обычно O (log n)) поиска слов, которые содержат подстроку.Таким образом, для каждой подстроки в B это будет O (n * log n)