У нас есть строка S, и мы хотим рассчитать количество отдельных строк, которые могут быть сформированы путем вращения строки.Количество отдельных вращающихся строк
Например: -
S = "аааа", здесь будет 1 строка {"аааа"}
S = "ABAB", здесь было бы 2 строки {"ABAB", "баба"}
Итак, есть алгоритм для решения этой проблемы в O (| S |) сложности, где | S | - длина строки.
Суффикс деревьев, детка!
Если строка - S. Создайте дерево суффикса для SS (S, связанное с S).
Найти количество уникальных подстрок длины S |. Уникальность вы получаете автоматически. Для длины | S | вам может потребоваться немного изменить дерево суффикса дерева (чтобы сохранить информацию о глубине), но выполнимо.
(Обратите внимание, что другой ответ johnsoe на самом деле квадратичен или, что еще хуже, зависит от реализации Set).
Что-то вроде этого должно сделать трюк.
public static int uniqueRotations(String phrase){
Set<String> rotations = new HashSet<String>();
rotations.add(phrase);
for(int i = 0; i < phrase.length() - 1; i++){
phrase = phrase.charAt(phrase.length() - 1) + phrase.substring(0, phrase.length() - 1);
rotations.add(phrase);
}
return rotations.size();
}
Это определенно не O (| S |) –
Вы можете решить эту проблему с помощью хеш-функций, используемых в Rabin-Karp algorithm.
Вы можете использовать подвижный хэш для обновления хеш-таблицы для всех подстрок размера | S | (полученное скольжением окна | S | через SS) в постоянное время (так, O (| S |) в целом).
Предполагая, что ваша строка исходит из алфавита постоянного размера, вы можете постоянно проверять хеш-таблицу для получения требуемой метрики.
Кажется, было бы проще, кода непосредственно в реальной практике, чем алгоритм дерева Укконена. +1 для обоих ответов в любом случае. – Matt
Что вы пробовали? Это кажется довольно простой проблемой, если вы сделаете попытку. –
Ну, в один прекрасный момент я решил повернуть строку и сохранить различные строки, сформированные в наборе, и ответ будет размером набора. – Mod
Я думал, что может быть алгоритм, который мог бы использовать функцию отказа KMP. – Mod