Периодические двоичные строки

Question

Существуют ли эффективные алгоритмы для проверки того, является ли двоичная строка периодической или нет?

Пусть S - двоичная строка, а H - множество подстрок S. Тогда S называется периодическим, если его можно получить, конкатенируя один или несколько раз, хотя бы один h в H, также h! = Юг

Answer 1

Начальная строка S длиной Len.Удвойте строку (на самом деле нам нужно S + половина S).Поиск вхождения начальной строки S в удвоенной строке SS, начиная со 2-й позиции, заканчивающейся в Len / 2 + 1. Если такое вхождение существует с позицией P, то S является периодическим с периодом P - 1.

S= abbaabbaabba Len = 12 SS = abbaabbaabbaabbaabbaabba

Поиск со 2-й по 7-ю позицию, S найден на P = 5, период = 4

S = abaabaabaabb SS = abaabaabaabbabaabaabaabb

Sне возникает в SS (кроме 1 и L + 1), период не существует

PS Примечание из-за полезного комментария Venkatesh: нам нужно добавить минимально возможную периодическую единицу, ее длинуL / 2 для строк четного размера и максимальный делитель L для строк нечетного размера (если длина является простым числом, строка не может быть периодической).Простые методы факторизации имеют сложность O (N ^ 1/2), более сложные - O (N ^ 1/4), поэтому иногда стоит факторизовать длину, чтобы избежать ненужного сравнения длинных строк.

Answer 2

Я почти уверен, что это можно улучшить, но я бы начал с разбиения длины S (я назову это L) на простые множители и проверки периода длины S / f. для каждого простого множителя f (len (h) должен делить len (S), и я не ищу кратчайшего возможного h, достаточно простого L / len (h)).

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

Answer 3

private static boolean isPeriodic(String string) {
int stringLength = string.length();
if (stringLength <= 1) {
    return false;
}
boolean flag = true;

for (int i = 1; i <= stringLength / 2; i++) {
if (string.length() % i == 0) {
if (flag && i > 1) {
    return flag;
}
flag = true;
for (int j = i; j < stringLength;) {

if ((j + i) <= stringLength) {

if (string.substring(0, i).equals(
        string.substring(j, j + i))) {
    j = j + i;
    continue;
} else {
    flag = false;
    break;

}
} else {
    break;
}

}
}

}
return flag;
}

Answer 4

Прежде всего, чтобы это произошло, необходимо, чтобы длина (h) разделяла длину (S).

Если k = length(S)/length(h), то для данного k легко проверить, является ли строка периодической.

Действительно, периодичность, если число, представленное S, делится на 100..0100..0 ... 100..0. Это число имеет длину длины (S), имеет k блоков одинаковой длины, и в каждом блоке установлен только самый старший бит.

Answer 5

Вот реализация алгоритма O(m + (n-1)) (где m - длина ввода, а n - длина цикла).

На основе алгоритма Кнута Морриса Пратта он выполняет итерацию по входной строке, проверяя, является ли подстрока input[0:i] повторяющимся шаблоном. Если во входной строке он находит символ, которого нет в шаблоне, то i обновляется, чтобы стать индексом этого символа. Это означает, что символы в строке сравниваются не более одного раза.

public static String findSequence(String input) {
  out: for (int i = 0; i < input.length();) {
    for (int j = i; j < input.length(); j++) {
      if(input.charAt(j % (i+1)) != input.charAt(j)) {
        i = j;
        continue out;
      }
    }
    return (String) input.subSequence(0, i + 1);
  }
  return ""; // Impossible
}