Я должен присвоить числа буквам a, b, c, d... z, чтобы для заданной строки и всего поиска анаграмм мы могли сделать это в o (n), используя хеш-поиск. Хеш-функция предположительно s[0]+s[1]+s[2]..s[n-1]. Анаграмма не зависит от позиции, поэтому нет необходимости умножать на позиционные степени, как в Рабине-Карпе.
Как присвоить числа буквам для поиска анаграмм с помощью модифицированного Рабина-Карпа
comment
что ты уже испробовал?
- person ti7 schedule 30.11.2020
comment
я читал обычный рабин карп, и мне кажется, что ключом может быть использование простых чисел, таких как 3 5 7 11 13 17 19 31, но я не могу доказать, что это правильно. мои небольшие дела, которые я написал, прошли, но это не доказывает их подлинность
- person MAG schedule 30.11.2020
Ответы (1)
Выберите какой-нибудь удобный простой модуль p (например, 231 − 1), а затем сопоставьте каждую букву со случайным числом от 0 до p−1 включительно. Можно показать, что, если предположить, что в каждом слове меньше p каждой буквы, вероятность ложного столкновения между двумя словами равна 1/p.
person
David Eisenstat
schedule
30.11.2020
как это показать господа? Итак, вы говорите, что присвоение алфавиту простого или непростого целого числа не имеет никакого значения с точки зрения вероятности?
- person MAG; 30.11.2020
@MAG Для любого числа c от 1 до p-1 включительно функция f(x) = cx mod p является однозначной картой целых чисел от 0 до p-1 включительно. Учитывая два разных слова, они имеют разное количество хотя бы одной буквы, а это означает, что вклада этой буквы в хэш достаточно, чтобы гарантировать, что разница хэшей равномерно распределена в 0..p-1.
- person David Eisenstat; 30.11.2020
