Оптимизация определенного регулярного выражения для равноудаленных букв

Question

Я работаю в Javascript, но я думаю, что это общий регулярный вопрос.

Я пишу скрипт, который ищет подстроки в длинной строке с равными расстояниями между буквами. Например, в тексте a11b22c33d44 у нас есть строка abcd с расстоянием 2 между каждыми двумя последовательными буквами.

Это тривиально, чтобы найти такие строки, используя поиск в регулярном выражении: для примера выше, мне просто нужно найти regexp /a.{2}b.{2}c.{2}d/. Итак, что я делаю сейчас, это следующее: если вы хотите найти слово и расстояние между последовательными буквами, я просто поставлю .{n} между ними (где n - это расстояние), скомпилируйте это как регулярное выражение и дайте ему сделать остальную работу ,

Это хорошо работает на практике, пока расстояние между буквами невелико - скажем, около 1000. Впоследствии он становится медленным. Он по-прежнему работает, но я надеюсь, что есть еще один способ более эффективного выполнения одного и того же поиска; Я не вижу очевидной причины, почему для больших разрывов она должна быть значительно медленнее (нам все равно нужно переходить весь текст только один раз, верно?)

Answer 1

Проблема в том, что точка может соответствовать почти любому, включая буквы , Каждый раз, когда он находит a, он должен сожрать следующие цифры n и попытаться сопоставить b, прежде чем сдаваться в этом матче. Это очень много усилий.

Вы должны быть более конкретными о том, что вы не хотите соответствовать. Например, если условия поиска всегда будет состоять только из букв, вы можете ускорить много, изменяя . к [^a-z]

/a[^a-z]{1000}b[^a-z]{1000}c[^a-z]{1000}d/i 

Другая возможность состоит в том, чтобы соответствовать ничего, кроме следующего необходимого характера:

/a[^b]{1000}b[^c]{1000}c[^d]{1000}d/i 

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

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

/\ba.{1000}b.{1000}c.{1000}d\b/i