Я ищу способ проверить, является ли строка периодической или не использующей JavaScript.
Пример строки для соответствия может быть 11223331122333. Принимая во внимание, что 10101 не должно совпадать.
Начиная с python, я использовал RegEx
/(.+?)\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.
Один из вариантов - продолжить использование регулярного выражения, но сделать его жадным, отбросив ?:
/^(.+)\1+$/
В зависимости от точных входных строк, это может уменьшить требуемое количество обратных трасс и ускорить сопоставление.
Если строка периодична:
Таким образом, мы можем сделать супер-жадный алгоритм, который берет последний элемент и проверяет вхождения до половины длины. Когда мы его найдем, мы проверяем, разделяет ли длина подстроки основную длину и только после этого мы будем тестировать строку.
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;
}
Есть ответ, заслуживающий упоминания его чистой красоты. Это не мое, я только адаптировал его из версии 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;
}
Прямой подход состоит в том, чтобы разделить строку на куски равного размера и проверить будет ли каждый патрон таким же, как первый кусок. Вот алгоритм что, увеличив размер куска от 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();
}
Я не тестировал скорость, хотя...