Поиск периодических строк с использованием строковых функций

Ответ 1

Идея приведенного ниже кода состоит в том, чтобы рассмотреть подстроки всех длин, исходную строку можно разделить на равномерно, и проверить, повторяются ли они по исходной строке. Простым методом является проверка всех делителей длины от 1 до квадратного корня длины. Они являются делителями, если деление дает целое число, которое также является дополнительным делителем. Например, для строки длиной 100 делители равны 1, 2, 4, 5, 10, а дополнительные делители 100 (не полезны в качестве длины подстроки, потому что подстрока появится только один раз), 50, 25, 20 (и 10, которые мы уже нашли).

function substr_repeats(str, sublen, subcount)
{
   for (var c = 0; c < sublen; c++) {
      var chr = str.charAt(c);
      for (var s = 1; s < subcount; s++) {
         if (chr != str.charAt(sublen * s + c)) {
            return false;
         }
      }
   }
   return true;
}

function is_periodic(str)
{
   var len = str.length;
   if (len < 2) {
      return false;
   }
   if (substr_repeats(str, 1, len)) {
      return true;
   }
   var sqrt_len = Math.sqrt(len);
   for (var n = 2; n <= sqrt_len; n++) { // n: candidate divisor
      var m = len / n; // m: candidate complementary divisor
      if (Math.floor(m) == m) {
         if (substr_repeats(str, m, n) || n != m && substr_repeats(str, n, m)) {
            return true;
         }
      }
   }
   return false;
}

К сожалению, нет метода String для сравнения с подстрокой другой строки (например, на языке C, который был бы strncmp(str1, str2 + offset, length)).

Скажите, что ваша строка имеет длину 120 и состоит из подстроки длиной 6, повторяемой 20 раз. Вы можете посмотреть на него также как состоящий из сублимации (длина подстроки) 12 повторяющихся 10 раз, сублитка 24 повторяется 5 раз, длина подрезанности 30 повторяется 4 раза или длина 60 повторений 2 раза (сублинты задаются основными коэффициентами 20 (2 * 2 * 5), применяемых в разных комбинациях к 6). Теперь, если вы проверите, будет ли ваша строка содержать длину 60 повторений 2 раза, а проверка не удалась, вы также можете быть уверены, что она не будет содержать какую-либо подслою, которая является делителем (т.е. Комбинацией простых коэффициентов) 60, в том числе 6. Другими словами, многие проверки, выполненные вышеуказанным кодом, являются излишними. Например, в случае длины 120 вышеописанный код проверяет (к счастью, большую часть времени не удается) следующие величины: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 (в этом порядке: 1, 60, 2, 40, 3, 30, 4, 24, 5, 20, 6, 15, 8, 12, 10). Из них необходимо только следующее: 24, 40, 60. Это 2 * 2 * 2 * 3, 2 * 2 * 2 * 5, 2 * 2 * 3 * 5, т.е. Комбинации простых чисел 120 ( 2 * 2 * 2 * 3 * 5) с одним из каждого (неповторяющегося) простого вынимаемого или, если хотите, 120/5, 120/3, 120/2. Итак, забывая на мгновение, что эффективная простая факторизация не является простой задачей, мы можем ограничить наши проверки повторяющихся подстрок на p подстроки длины длины сублима /p, где p - простой коэффициент длины. Ниже приведена простейшая нетривиальная реализация:

function substr_repeats(str, sublen, subcount) { see above }

function distinct_primes(n)
{
   var primes = n % 2 ? [] : [2];
   while (n % 2 == 0) {
      n /= 2;
   }
   for (var p = 3; p * p <= n; p += 2) {
      if (n % p == 0) {
         primes.push(p);
         n /= p;
         while (n % p == 0) {
            n /= p;
         }
      }
   }
   if (n > 1) {
      primes.push(n);
   }
   return primes;
}

function is_periodic(str)
{
   var len = str.length;
   var primes = distinct_primes(len);
   for (var i = primes.length - 1; i >= 0; i--) {
      var sublen = len / primes[i];
      if (substr_repeats(str, sublen, len / sublen)) {
         return true;
      }
   }
   return false;
}

Попробовав этот код на моем Linux-ПК, я удивился: в Firefox он был намного быстрее, чем первая версия, но на Chromium он был медленнее, и он стал быстрее только для строк с длинами в тысячах. Наконец, я выяснил, что проблема связана с массивом, который distinct_primes() создает и переходит к is_periodic(). Решение заключалось в том, чтобы избавиться от массива, объединив эти две функции. Код ниже и результаты теста находятся на http://jsperf.com/periodic-strings-1/5

function substr_repeats(str, sublen, subcount) { see at top }

function is_periodic(str)
{
   var len = str.length;
   var n = len;
   if (n % 2 == 0) {
      n /= 2;
      if (substr_repeats(str, n, 2)) {
         return true;
      }
      while (n % 2 == 0) {
         n /= 2;
      }
   }
   for (var p = 3; p * p <= n; p += 2) {
      if (n % p == 0) {
         if (substr_repeats(str, len / p, p)) {
            return true;
         }
         n /= p;
         while (n % p == 0) {
            n /= p;
         }
      }
   }
   if (n > 1) {
      if (substr_repeats(str, len / n, n)) {
         return true;
      }
   }
   return false;
}

Помните, что таймеры, собранные jsperf.org, являются абсолютными, и что разные экспериментаторы с разными машинами будут способствовать различным комбинациям каналов. Вам нужно отредактировать новую личную версию эксперимента, если вы хотите надежно сравнить два механизма JavaScript.

Ответ 2

Один из вариантов - продолжить использование регулярного выражения, но сделать его жадным, отбросив ?:

/^(.+)\1+$/

В зависимости от точных входных строк, это может уменьшить требуемое количество обратных трасс и ускорить сопоставление.

Ответ 3

Если строка периодична:

• Последний элемент также будет последним элементом периода
• Длина периода будет разделять длину строки

Таким образом, мы можем сделать супер-жадный алгоритм, который берет последний элемент и проверяет вхождения до половины длины. Когда мы его найдем, мы проверяем, разделяет ли длина подстроки основную длину и только после этого мы будем тестировать строку.

function periodic(str){
    for(var i=0; i<=str.length/2; i++){
        if(str[i] === str[str.length-1] && str.length%(i+1) === 0){
            if (str.substr(0,i+1).repeat(str.length/(i+1)) === str){
        return true;
            }
        }
    }
    return false;
}

Ответ 4

Есть ответ, заслуживающий упоминания его чистой красоты. Это не мое, я только адаптировал его из версии Python, которая находится здесь: Как узнать, повторяется ли строка в Python?

function is_periodic(s)
{
   return (s + s.substring(0, s.length >> 1)).indexOf(s, 1) > 0;
}

К сожалению, скорость не наравне с красотой (а также красота немного поправилась в адаптации от Python, так как indexOf() имеет параметр запуска, но не параметр остановки). Сравнение с решением (ами) регулярных выражений и функциями моего другого ответа здесь. Даже со строками случайной длины в [4, 400] на основе небольшого 4-символьного алфавита функции моего другого ответа выполняются лучше. Это решение быстрее, чем решение регулярных выражений.

Это решение можно было бы назвать "решением фазовой перестройки" . Строка рассматривается как волна, которая сама по себе идентична сдвигу фазы.

Преимущество этого решения над одним из моих ответов заключается в том, что его можно легко адаптировать для возврата кратчайшей повторяющейся подстроки, например:

function repeating_substr(s)
{
    period = (s + s.substring(0, s.length >> 1)).indexOf(s, 1);
    return period > 0 ? s.substr(0, period) : null;
}

Ответ 5

Прямой подход состоит в том, чтобы разделить строку на куски равного размера и проверить будет ли каждый патрон таким же, как первый кусок. Вот алгоритм что, увеличив размер куска от 1 до длины /2, пропуская размеры блоков которые не делят чисто длину.

function StringUnderTest (str) {
    this.str = str;
    this.halfLength = str.length / 2;
    this.period = 0;
    this.divideIntoLargerChunksUntilPeriodicityDecided = function () {
        this.period += 1;
        if (this.period > this.halfLength)
            return false;
        if (this.str.length % this.period === 0)
            if (this.currentPeriodOk())
                return true;
        return this.divideIntoLargerChunksUntilPeriodicityDecided();
    };
    this.currentPeriodOk = function () {
        var patternIx;
        var chunkIx;
        for (chunkIx=this.period; chunkIx<this.str.length; chunkIx+=this.period)
            for (patternIx=0; patternIx<this.period; ++patternIx)
                if (this.str.charAt(patternIx) != this.str.charAt(chunkIx+patternIx))
                    return false;
        return true;
    };
}

function isPeriodic (str) {
    var s = new StringUnderTest(str);
    return s.divideIntoLargerChunksUntilPeriodicityDecided();
}

Я не тестировал скорость, хотя...