Решение
Следующий фрагмент генерирует шаблон, который выполняет работу ( см. Его запуск на ideone.com ):
// splits at indices that are triangular numbers
class TriangularSplitter {
// asserts that the prefix of the string matches pattern
static String assertPrefix(String pattern) {
return "(?<=(?=^pattern).*)".replace("pattern", pattern);
}
// asserts that the entirety of the string matches pattern
static String assertEntirety(String pattern) {
return "(?<=(?=^pattern$).*)".replace("pattern", pattern);
}
// repeats an assertion as many times as there are dots behind current position
static String forEachDotBehind(String assertion) {
return "(?<=^(?:.assertion)*?)".replace("assertion", assertion);
}
public static void main(String[] args) {
final String TRIANGULAR_SPLITTER =
"(?x) (?<=^.) | measure (?=(.*)) check"
.replace("measure", assertPrefix("(?: notGyet . +NBefore +1After)*"))
.replace("notGyet", assertPrefix("(?! \\1 \\G)"))
.replace("+NBefore", forEachDotBehind(assertPrefix("(\\1? .)")))
.replace("+1After", assertPrefix(".* \\G (\\2?+ .)"))
.replace("check", assertEntirety("\\1 \\G \\2 . \\3"))
;
String text = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
System.out.println(
java.util.Arrays.toString(text.split(TRIANGULAR_SPLITTER))
);
// [a, bc, def, ghij, klmno, pqrstu, vwxyzAB, CDEFGHIJ, KLMNOPQRS, TUVWXYZ]
}
}
Обратите внимание, что в этом решении используются методы, уже описанные в моей серии статей о регулярных выражениях. Единственная новая вещь здесь - это \G и прямые ссылки.
Ссылки
Это краткое описание основных конструкций регулярных выражений:
(?x) - это встроенный флаг модификатор , чтобы включить режим свободный интервал , где неэкранированные пробелы игнорируются (и можно использовать # для комментариев). ^ и $ - начало и конец строки якоря . \G это конец предыдущего матча якорь. | обозначает чередование (т.е. "или"). ? в качестве спецификатора повторения обозначает необязательно (т.е. ноль или один из). В качестве количественного показателя повторения, например, .*? обозначает, что повторение * (т.е. ноль или более) составляет неохотно / не жадное. (…) используются для группировки . (?:…) - группа без захвата. Группа захвата сохраняет строку, которой она соответствует; он позволяет, помимо прочего, сопоставлять ссылки назад / вперед / вложенные (например, \1). (?=…) является положительным прогноз ; он смотрит вправо, чтобы утверждать, что есть совпадение данного шаблона. (?<=…) является положительным lookbehind ; это смотрит налево. (?!…) является отрицательным прогнозом; он смотрит вправо, чтобы утверждать, что не соответствует шаблону.
Похожие вопросы
Объяснение
Шаблон соответствует утверждениям нулевой ширины. Довольно сложный алгоритм используется, чтобы утверждать, что текущая позиция является треугольным числом . Есть 2 основных варианта:
(?<=^.), то есть мы можем посмотреть назад и увидеть начало строки на расстоянии одной точки
- Это соответствует индексу 1 и является важной отправной точкой для остальной части процесса
- В противном случае мы
measure восстанавливаем, как было выполнено последнее совпадение (используя \G в качестве контрольной точки), сохраняя результат измерения в "до" \G и "после" \G групп захвата. Затем мы check, если текущая позиция является той, которая предписана измерением, чтобы найти, где должно быть сделано следующее совпадение.
Таким образом, первая альтернатива является тривиальным «базовым случаем», а вторая альтернатива устанавливает, как сделать все последующие совпадения после этого. У Java нет пользовательских групп, но вот семантика для 3 групп захвата:
\1 захватывает строку «до» \G\2 фиксирует некоторую строку "после" \G- Если длина
\1, например, 1 + 2 + 3 + ... + k , тогда длина \2 должна составлять k .
- Следовательно,
\2 . имеет длину k + 1 и должен быть следующей частью в нашем split!
\3 захватывает строку справа от нашей текущей позиции
- Следовательно, когда мы можем
assertEntirety на \1 \G \2 . \3, мы сопоставляем и устанавливаем новый \G
Вы можете использовать математическую индукцию, чтобы строго доказать правильность этого алгоритма.
Чтобы проиллюстрировать, как это работает, давайте разберем пример. Давайте возьмем abcdefghijklm в качестве входных данных и скажем, что мы уже частично откололись [a, bc, def].
\G we now need to match here!
↓ ↓
a b c d e f g h i j k l m n
\____1____/ \_2_/ . \__3__/ <--- \1 G \2 . \3
L=1+2+3 L=3
Помните, что \G отмечает конец последнего совпадения, и это происходит по индексам треугольных чисел. Если \G произошло в 1 + 2 + 3 + ... + k , то следующее совпадение должно быть на k + 1 позициях после \G, чтобы быть треугольным числом индекс.
Таким образом, в нашем примере, где \G - это то место, где мы только что разделили def, мы измерили, что k = 3 , и следующее совпадение получит ghij, как и ожидалось.
Чтобы \1 и \2 были построены в соответствии с вышеприведенной спецификацией, мы в основном делаем while «петлю»: до тех пор, пока это notGyet, мы считаем до k следующим образом:
+NBefore, т.е. мы расширяем \1 на один forEachDotBehind+1After, т.е. мы расширяем \2 всего на один
Обратите внимание, что notGyet содержит ссылку forward на группу 1, которая будет определена позже в шаблоне. По сути, мы делаем цикл, пока \1 "не попадет" \G.
Заключение
Излишне говорить, что это конкретное решение имеет ужасную производительность. Механизм регулярных выражений запоминает WHERE последнего сопоставления (с \G) и забывает HOW (т. Е. Все группы захвата сбрасываются при следующей попытке сопоставления). Наш шаблон должен затем реконструировать HOW (ненужный шаг в традиционных решениях, где переменные не так «забывчивы») путем тщательного построения строк путем добавления одного символа за раз (что составляет O(N^2)). , Каждое простое измерение является линейным, а не постоянным временем (поскольку оно выполняется в виде совпадения строк, где длина является фактором), и, в дополнение к этому, мы делаем много измерений, которые являются избыточными (то есть, чтобы увеличить на единицу, нам нужно сначала сопоставить заново) что у нас уже есть).
Вероятно, есть много "лучших" решений для регулярных выражений, чем это. Тем не менее, сложность и неэффективность этого конкретного решения должны справедливо предполагать, что регулярное выражение не предназначено для такого типа сопоставления с образцом.
Тем не менее, для целей обучения, это абсолютно замечательная проблема, поскольку в исследовании и формулировании ее решений имеется огромное количество знаний. Надеюсь, это конкретное решение и его объяснение были поучительными.