Поиск строки для анаграммы другой строки?

Question

Поиск строки для анаграммы другой строки?

Я пытаюсь найти подстроку из строки text это анаграмма в строку pattern,

Мой вопрос:
Может ли Алгоритм Рабина-Карпа приспособиться к этой цели? Или есть лучшие алгоритмы?

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

Обновить: Я слышал, что есть худший случай O (n²) алгоритм, использующий пространство O (1). Кто-нибудь знает, что это за алгоритм?

Обновление 2: Для справки вот псевдокод для алгоритма Рабина-Карпа:

function RabinKarp(string s[1..n], string sub[1..m])
hsub := hash(sub[1..m]);  hs := hash(s[1..m])
for i from 1 to n-m+1
if hs = hsub
if s[i..i+m-1] = sub
return i
hs := hash(s[i+1..i+m])
return not found

При этом используется скользящая хеш-функция, позволяющая вычислить новый хеш в O (1),
таким образом, общий поиск составляет O (нм) в худшем случае, но с хорошей хэш-функцией в лучшем случае O (m + n). Есть ли скользящая хеш-функция, которая будет производить few collisions при поиске анаграммы строки?

4

algorithm anagram c++hash string

Решение

Другие решения

Один из вариантов — сохранить скользящее окно, содержащее гистограмму букв, содержащихся в окне. Если эта гистограмма когда-либо окажется равной гистограмме символа для строки, чья анаграмма должна быть найдена, то вы знаете, что то, на что вы смотрите, совпадает и может вывести ее. Если нет, вы знаете, что то, что у вас есть, не может быть совпадением.

Более конкретно, создайте ассоциативный массив A, сопоставляющий символы с их частотами. Если вы хотите найти анаграмму строки P, прочитайте первую | P | символы из текстовой строки T в A и построить гистограмму соответствующим образом. Вы можете сдвинуть окно на один шаг вперед и обновить A в O (1) операциях с ассоциативным массивом, уменьшив частоту, связанную с первым символом в окне, а затем увеличивая частоту, связанную с новым символом, который скользнул в окно.

Если гистограммы текущего окна и окна шаблона очень разные, то вы сможете сравнить их довольно быстро. В частности, скажем, что ваш алфавит Σ. В худшем случае, сравнения двух гистограмм бы время O (| Σ |), так как вы должны проверить каждый символ / пары частот в гистограмме с эталонной гистограмме. В лучшем случае, тем не менее, вы сразу найдете символ, который вызывает несоответствие между А и эталонной гистограммой, поэтому вам не нужно будет рассматривать много символов в целом.

Теоретически для этого подхода время выполнения в наихудшем случае равно O (| T || Σ | + | P |), поскольку для построения исходной гистограммы необходимо выполнить O (n), а затем выполнить Σ в худшем случае. на персонажа в T. Тем не менее, я ожидаю, что это, вероятно, намного быстрее на практике.

Надеюсь это поможет!

8

Создайте массив letter_counts из 26 дюймов (равный нулю) и переменную missing_count для хранения количества пропущенных букв.
Для каждой буквы в подстроке уменьшите соответствующий int для letter_counts на 1 и увеличьте missing_count на 1 (таким образом, missing_count в конечном итоге будет равен размеру подстроки).
Скажем, подстрока имеет размер k. Посмотрите на первые k букв строки. увеличить значение int для letter_counts на 1. Если после увеличения значение равно <= 0, уменьшить пропущенное_счет на 1.
Теперь мы «катимся вперед» по веревке вот так.
а. удалите букву, ближайшую к началу окна, уменьшите связанный элемент letter_counts. Если после уменьшения мы имеем < 0, затем увеличиваем отсутствующий счетчик на 1.
б. добавьте первую букву строки за окном. увеличить связанный член letter_counts. Если после увеличения у нас есть int <= 0, тогда уменьшите значение пропущенного_счета на 1.

Если в какой-то момент пропущено число == 0, у нас есть анаграмма строки поиска в нашем окне.

Инвариант, который мы поддерживаем, заключается в том, что missing_count содержит количество букв в нашей подстроке, которых нет в нашем окне. Когда это ноль, буквы в нашем окне точно соответствуют буквам в нашей подстроке.

Это Theta (n) — линейное время, так как мы смотрим на каждую букву ровно один раз.

— редактировать —

Буква_счета должна хранить только отдельные буквы подстроки и должна содержать только целые числа размером с подстроку (со знаком). Таким образом, использование памяти является линейным по размеру подстроки, но постоянным по размеру строки.

3

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

Чтобы избежать совпадения совпадений символов, если символ найден в text массив, его соответствующий индекс массива удаляется, эффективно сокращая время до завершения сканирования массива с каждым совпадением, в то же время гарантируя, что text содержащий 2x ‘B’ не будет соответствовать pattern с 3x ‘B’.

Для повышения производительности вы можете отсканировать обе строки перед подсчетом символов и составить список алфавитных букв в каждой строке, а затем сравнить эти списки, чтобы выяснить, есть ли какие-либо расхождения (например, попытаться найти буква «z» в «яблоке»), и, если есть, пометьте строку как «Анаграмма невозможна».

0

Источник

Accepted Answer

Вычислить хэш шаблона, который не зависит от порядка букв в шаблоне (например, используйте сумму кодов символов для каждой буквы). Затем примените к тексту ту же хеш-функцию, что и в «Рабине-Карпе». Если хэши совпадают, вам необходимо выполнить полную проверку шаблона по отношению к текущему окну в тексте, потому что хеш может столкнуться и с другими значениями.

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

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

В качестве примера предположим, что вы вычисляете хэш букв «a» — «z» как 64-разрядное значение без знака. Используйте таблицу как это:

символ | код | код^-1
-------+------+---------------------
а | 3 | 12297829382473034411
б | 5 | 14757395258967641293
с | 7 | 7905747460161236407
д | 11 | 3353953467947191203
е | 13 | 5675921253449092805
...
z | 103 | 15760325033848937303

Мультипликативное обратное N это число, которое дает 1 при умножении на п, по модулю некоторое число. Модуль здесь равен 2⁶⁴, так как вы используете 64-битные числа. Так, 5 * 14757395258967641293 должно быть 1, например. Это работает, потому что вы просто умножение в GF(2⁶⁴).

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

Начните кодирование с числа 3, потому что 2 совпадает с размером целого числа (степень 2 на любом процессоре, на котором вы работаете) и не может быть инвертировано.

8