使用regex拆分长度不同的字符串

解决方案

下面的代码段生成执行该作业的模式( see it run on 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]
  }
}

注意,这个解决方案使用的技术已经在我的regex系列文章中介绍过。这里唯一的新鲜事就是 \G 并转发参考。

工具书类

这是对使用的基本regex构造的简要描述:

• (?x) 是嵌入的标志 modifier 启用 free-spacing 模式,其中未捕获的空白被忽略(和 # 可用于注释)。
• ^ 和 $ 是行首和行尾 anchors . \g 是 end-of-previous match 锚。
• | 表示 alternation (即“或”)。
• ? 作为重复说明符表示 optional (即0或1)。作为重复量词,例如 .*? 它表示 * (即零或更多)重复是 reluctant 非贪婪。
• (…) 用于 grouping . (?:…) 是非捕获组。捕获组保存它匹配的字符串;它允许在后退/前进/嵌套引用(例如 \1 )
• (?=…) 是正的 lookahead ;它看起来有权断言给定模式存在匹配。 (?<=…) 是正的 了望 它向左看。
• (?!…) 是一个 消极的 展望未来;它有权断言 不是 图案的匹配。

相关问题

• 文章 [nested-reference] 系列:
  • How does this regex find triangular numbers?
  • How can we match a^n b^n with Java regex?
  • How does this Java regex detect palindromes?
• How does the regular expression (?<=#)[^#]+(?=#) work?

解释

模式匹配零宽度断言。使用相当复杂的算法来断言当前位置是 triangular number . 主要有两种选择:

• (?<=^.) 也就是说,我们可以向后看,看到一个点以外的字符串的开头。
  • 这与索引1匹配,并且是流程其余部分的关键起点。
• 否则,我们 measure 重新构造上次匹配的方式(使用 \g 作为参考点),将测量结果存储在“之前”中。 \g “后” \g 正在捕获组。然后我们 check 如果当前位置是由测量规定的位置,以确定下一个匹配的位置。

因此,第一个备选方案是简单的“基本情况”,第二个备选方案设置如何在之后进行所有后续匹配。Java没有自定义命名组,但这里是3个捕获组的语义:

• 1 捕获字符串“before” \g
• \2 捕获一些字符串“after” \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 仅仅一个

注意 诺格特 包含一个 向前地 引用稍后在模式中定义的组1。基本上我们做循环直到 1 “点击” \g .

结论

不用说,这个特定的解决方案的性能很差。regex引擎只记住 在哪里? 最后一场比赛是 \g 忘记 同质光波导 (即,下次尝试匹配时,所有捕获组都将重置)。我们的模式必须重建 同质光波导 (传统解决方案中不必要的一步,其中变量不是那么“健忘”),通过一次附加一个字符(即 O(N^2) )每一个简单的测量都是线性的,而不是恒定的时间(因为它是作为一个字符串匹配完成的,其中长度是一个因子),此外,我们还进行了许多冗余的测量(即,要扩展一个,我们需要首先重新匹配我们已经拥有的)。

可能有很多比这个更好的regex解决方案。尽管如此,这个特定的解决方案的复杂性和低效性应该合理地表明regex不是为这种模式匹配而设计的。

也就是说,为了学习的目的,这是一个绝对美妙的问题,因为在研究和制定解决方案时有大量的知识。希望这个特别的解决方案及其解释具有指导意义。

regex的目的是识别模式。在这里,您不搜索模式,而是搜索长度分割。 所以regex不合适 .

这是可能的,但不是用一个正则表达式:找到第一个 n 使用regex的字符,可以使用:“^(.”{ n } *

所以,您可以使用该regex搜索第一个字符。 然后,创建一个子字符串,并搜索接下来的2个字符。 等。

就像@splash所说的,这会使代码变得更复杂、更不正式,因为您使用regex是为了超出它们的目的。

String a = "hellohowareyou??";
int i = 1;

    while(true) {

        if(i >= a.length()) {
            System.out.println(a);
            break;
        }

        else {
            String b = a.substring(i++);
            String[] out = a.split(Pattern.quote(b) + "$");
            System.out.println(out[0]);
            a = b;
            if(b.isEmpty())
                break;
        }

    }