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