Как найти все циклически сдвинутые строки в заданном входе?

Question

Это упражнение по кодированию. Предположим, мне нужно решить, создана ли одна строка циклическим сдвигом другой. Например: cab - это циклический сдвиг abc, а cba - нет.

Учитывая две строки s1 и s2, мы можем сделать это следующим образом:

if (s1.length != s2.length)
  return false
for(int i = 0; i < s1.length(); i++)
  if ((s1.substring(i) + s1.substring(0, i)).equals(s2))
    return true
return false

Теперь, что если у меня есть массив строк и я хочу найти все строки, которые являются циклическими сдвигами друг друга? Например: ["abc", "xyz", "yzx", "cab", "xxx"] -> ["abc", "cab"], ["xyz", "yzx"], ["xxx"]

Похоже, я должен проверить все пары строк. Есть ли «лучший» (более эффективный) способ сделать это?

Answer 1

В качестве начала вы можете узнать, является ли строка s1 поворотом строки s2 с помощью одного вызова метода contains (), например:

public boolean isRotation(String s1, String s2){
    String s2twice = s2+s2;
    return s2twice.contains(s1);
}

А именно, если s1 является «вращением»и s2 это "otationr", concat дает вам "otationrotationr", который действительно содержит s1.

Теперь, даже если мы предположим, что это линейно или близко к нему (что, например, невозможно при использовании Рабина-Карпа), у вас все равно останется O (n ^ 2) парных сравнений, которые могутбыть слишком много.

То, что вы могли бы сделать, это создать хеш-таблицу, где отсортированное слово является ключом, а список публикации содержит все слова из вашего списка, которые, если отсортированы, дают ключ (т.е. ключ («bca») и ключ («cab») оба должны возвращать «abc»):

private Map<String, List<String>> index;
    /* ... */
public void buildIndex(String[] words){
    for(String word : words){
        String sortedWord = sortWord(word);
        if(!index.containsKey(sortedWord)){
            index.put(sortedWord, new ArrayList<String>());
        }
        index.get(sortedWord).add(word);
    }
}

CAVEAT: Хеш-таблица будет содержать для каждого ключа все слова, которые имеют абсолютно одинаковые буквы, встречающиеся втакое же количество раз (не только повороты, т. е. «abba» и «baba» будут иметь одинаковый ключ, но isRotation («abba», «baba») вернет false).

Но как только вы построите этот индекс, вы можете значительно сократить количество пар, которые вам нужно учитывать: если вы хотите, чтобы все повороты для «bca» вам просто нужно отсортировать («bca»), посмотрите еговверх в хеш-таблице и проверьте (если хотите, используя метод isRotation выше), являются ли слова в списке публикаций результатом поворота или нет.

Answer 2

Если строки короткие по сравнению с количеством строк в списке, вы можете добиться значительных успехов, повернув все строки в некоторую нормальную форму (например, лексикографический минимум).Затем сортируйте лексикографически и находите серии из одной и той же строки.Это O (n log n), я думаю ... пренебрегая длинами строк.Может быть, кое-что попробовать.

Answer 3

Вы можете повернуть все строки в нормализованную форму, используя алгоритм Бута (https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation) за время O (s), где s - длина строки.

Затем можно использоватьнормализованная форма как ключ в HashMap (где значением является набор вращений, видимых во входных данных). Вы можете заполнить этот HashMap за один проход над данными, т. е. для каждой строки

• вычислите нормализованную форму
• проверьте, содержит ли HashMap нормализованную форму в качестве ключа - если нет, вставьте пустой набор в этот ключ
• добавьте строку в набор в HashMap

Затем вам просто нужно вывести значения HashMap. Это дает общее время выполнения алгоритма O (n * s) - где n - количество слов, а s - средняя длина слова. Общее пространствоиспользование также O (n * s).

Answer 4

Я думаю, что комбинация ответов Patrick87 и savinos имела бы достаточный смысл.В частности, в псевдокоде на языке Java:

List<String> inputs = ["abc", "xyz", "yzx", "cab", "xxx"];
Map<String,List<String>> uniques = new Map<String,List<String>>();
for(String value : inputs) {
    String normalized = normalize(value);
    if(!uniques.contains(normalized)) {
        unqiues.put(normalized, new List<String>());
    }
    uniques.get(normalized).add(value);
}
// you now have a Map of normalized strings to every string in the input
// that is "equal to" that normalized version

Нормализация строки, как заявлено Патриком87, может быть лучше всего выполнена путем выбора поворота строки, что приводит к наименьшему лексографическому порядку.

Однако стоит отметить, что «лучший» алгоритм, вероятно, сильно зависит от входных данных ... количества строк, длины этих строк, количества дубликатов и т. Д.

Answer 5

Рассмотрите возможность создания автомата для каждой строки, с которой вы хотите проверить.

Каждый автомат должен иметь одну точку входа для каждого возможного символа в строке и переходы для каждого символа, а также дополнительный переход от конца к началу.

Вы можете еще больше повысить производительностьесли вы объединили автоматы.

Answer 6

Что касается способа поиска пар в таблице, то может быть гораздо лучший способ, но в первую очередь я решил отсортировать таблицу и применить проверку для соседней пары.

Это намного лучше и проще, чем проверять каждую строку с каждой другой строкой в ​​таблице