Алкоголик, хулиган, тунеядец.

Наибольший вклад в теги

Все теги (8)

Лучшие ответы пользователя

Все ответы (1)
  • Как правильно сравнить массивы и оценить их схожесть?

    На самом деле, я тут подумал, и придумал получше Фурье.
    Например, если вы говорите, что массивы одинаковы с точностью до поворота, то можно и надо сравнивать их на эквивалентность (я не говорю про процентную схожесть, тут сложнее), то можно интерпретировать их как строчки, и составить такую, например:
    S + "$" + T + T,
    где S -- один массив, а после разделителя два раза подряд записанный правый массив. Тогда тут достаточно запустить посчиать префикс-функцию с помощью алгоритма Кнута-Морриса-Пратта за линейное время. Если же интересуют схожие куски, то надо копать в сторону суффиксных массивов и деревьев, если хочется линейное время
    Ответ написан
    1 комментарий

Лучшие вопросы пользователя

Все вопросы (3)