Циклические Слова
Постановка задачи
Мы можем думать о циклическом слове как о слове, написанном по кругу. Чтобы представить циклическое слово, мы выбираем произвольную начальную позицию и читаем символы по часовой стрелке. Таким образом, «картинка» и «турепик» являются представлениями одного и того же циклического слова.
Вам дается слово String [], каждый элемент которого является представлением циклического слова. Возвращает количество различных циклических слов, которые представлены.
Самые быстрые победы (Big O, где n = количество символов в строке)
word-puzzle
counting
fastest-algorithm
eggonlegs
источник
источник
Ответы:
питон
Вот мое решение. Я думаю, что это все еще может быть O (n 2 ), но я думаю, что средний случай намного лучше, чем это.
В основном это работает путем нормализации каждой строки, так что любое вращение будет иметь одинаковую форму. Например:
Нормализация выполняется путем поиска минимального символа (по коду символа) и поворота строки, чтобы символ находился в последней позиции. Если этот символ встречается более одного раза, используются символы после каждого вхождения. Это дает каждому циклическому слову каноническое представление, которое можно использовать в качестве ключа на карте.
Нормализация равна n 2 в худшем случае (где каждый символ в строке одинаков, например
aaaaaa
), но в большинстве случаев будет только несколько случаев, и время выполнения будет ближе кn
.На моем ноутбуке (двухъядерный Intel Atom @
/usr/share/dict/words
1,66 ГГц и 1 ГБ оперативной памяти) его запуск (234937 слов со средней длиной 9,5 символов) занимает около 7,6 секунды.источник
Python (3) снова
Метод, который я использовал, заключался в вычислении скользящего хэша каждого слова, начиная с каждого символа в строке; поскольку это скользящий хеш, требуется O (n) (где n - длина слова), чтобы вычислить все n хешей. Строка обрабатывается как число base-1114112, что гарантирует уникальность хэшей. (Это похоже на решение Haskell, но более эффективно, поскольку оно проходит через строку только дважды.)
Затем для каждого входного слова алгоритм проверяет свой самый низкий хеш, чтобы увидеть, находится ли он уже в наборе увиденных хэшей (набор Python, таким образом, поиск равен O (1) в размере набора); если это так, то слово или один из его поворотов уже видели. В противном случае он добавляет этот хэш к набору.
Аргумент командной строки должен быть именем файла, содержащего одно слово в строке (например
/usr/share/dict/words
).источник
Haskell
Не уверен насчет эффективности этого, скорее всего, довольно плохо. Идея состоит в том, чтобы сначала создать все возможные повороты всех слов, сосчитать значения, которые однозначно представляют строки, и выбрать минимум. Таким образом, мы получаем число, уникальное для циклической группы.
Мы можем сгруппировать по этому номеру и проверить количество этих групп.
Если n - это количество слов в списке, а m - это длина слова, тогда вычисляется «номер циклической группы» для всех слов:
O(n*m)
сортировкаO(n log n)
и группировкаO(n)
.источник
Mathematica
Решили начать снова, теперь, когда я понимаю правила игры (я думаю).
Словарь из 10000 слов уникальных случайно составленных «слов» (только в нижнем регистре) длиной 3. Аналогичным образом были созданы другие словари, состоящие из строк длиной 4, 5, 6, 7 и 8.
g
принимает текущую версию словаря для проверки. Верхнее слово объединяется с циклическими вариантами (если они есть). Слово и его совпадения добавляются в список выводаout
обработанных слов. Выходные слова удаляются из словаря.f
пробегает словарь всех слов.Пример 1 : фактические слова
Пример 2 : Искусственные слова. Словарь строк длины 3. Во-первых, время. Тогда количество слов цикла.
Время как функция длины слова . 10000 слов в каждом словаре.
Я не особенно знаю, как интерпретировать результаты в терминах О. Проще говоря, время примерно удваивается от словаря из трех символов до словаря из четырех символов. Время увеличивается почти незаметно с 4 до 8 символов.
источник
Это можно сделать за O (n), избегая квадратичного времени. Идея состоит в том, чтобы построить полный круг, пересекающий основную строку дважды. Таким образом, мы строим «amazingamazin» как строку полного круга, чтобы проверить все циклические строки, соответствующие «удивительным».
Ниже приведено решение Java:
источник
Я не знаю, насколько это эффективно, но это мой первый крэк.
источник
Perl
не уверен, что я понимаю проблему, но это соответствует примеру @dude, опубликованному в комментариях, по крайней мере. пожалуйста, исправьте мой заведомо неверный анализ.
для каждого слова W в заданных N словах списка строк вы должны пройти все символы W в худшем случае. Я должен предположить, что хэш-операции выполняются в постоянное время.
источник