使用正则表达式拆分长度不同的字符串

Question

我不知道是否可以使用正则表达式实现这个功能。我只是想问一下，以防有人知道答案。

我有一个字符串 string="hellohowareyou??"。我需要像这样分割它

[h, el, loh, owar, eyou?, ?]。

分割的方法是第一个字符串长度为1，第二个字符串长度为2，以此类推，最后一个字符串将拥有剩余的字符。我可以轻松地使用一个函数来完成这个操作，但无法使用正则表达式。

public ArrayList<String> splitString(String s)
    {
        int cnt=0,i;
        ArrayList<String> sList=new ArrayList<String>();
        for(i=0;i+cnt<s.length();i=i+cnt)
        {
         cnt++;
         sList.add(s.substring(i,i+cnt));    
        }
        sList.add(s.substring(i,s.length()));
        return sList;
    }

我只是好奇是否可以使用正则表达式来完成这样的事情。

- Emil

---

听起来像是“有人能给我展示一下，如何把它变得复杂吗？”;-) - splash

不要紧，如果你把它搞得很复杂，我只是在学习正则表达式的可能性而已。 - Emil

我个人非常真诚地感谢您提出这个问题。在尝试解决它的过程中，我感到很有趣，学到了很多知识，并且还第一次使用了前向引用。我已经反复修改了我的答案，并认为每次都得到了更好的解决方案。如果将来我想出更加优美的解决方案，我可能会再次回顾这个问题。 - polygenelubricants

@poly：其实应该是我感谢你。事实上，你回答了我大部分的问题，我已经成为了你的忠实粉丝。如果你不介意的话，我想问你一件事情。'polygenelubricants'是什么意思？ - Emil

在Java中，"polygenelubricants".hashCode()是Integer.MIN_VALUE。在二进制补码表示中，最负值是唯一的，因为它没有正数对应项。也就是说，在Java中，Math.abs(Integer.MIN_VALUE)是一个负数。该字符串的来源归功于Josh Bloch，他在其中一个谜题中使用了它。 - polygenelubricants

Answer 1

解决方案

以下代码片段生成了完成任务的模式（在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) 是内嵌标志 modifier，用于启用 free-spacing 模式，在该模式下未转义的空格将被忽略（并且 # 可以用于注释）。
• ^ 和 $ 分别是行首和行尾的锚点 anchors。 \G 是end-of-previous match 锚点。
• | 表示alternation（即“或”）。
• ? 作为重复修饰符表示 optional（即零个或一个）。作为重复量词在例如 .*? 中时，表示 *（即零个或多个）的重复是reluctant/非贪婪的。
• (…) 用于grouping。 (?:…) 是非捕获组。捕获组保存它匹配的字符串；它允许在反向引用/前向引用/嵌套引用（例如 \1）中进行匹配。
• (?=…) 是正向lookahead；它向右查找以断言给定模式的匹配项。 (?<=…) 是正向lookbehind，它向左查找。
• (?!…) 是negative lookahead；它向右查找以断言不存在某个模式的匹配项。

相关问题

• 嵌套引用系列文章：
  • 这个正则表达式如何找到三角数？
  • 如何使用Java正则表达式匹配a^n b^n？
  • 这个Java正则表达式如何检测回文？
• 正则表达式(?<=#)[^#]+(?=#)是如何工作的？

---

解释

该模式匹配零宽度断言。使用相当复杂的算法来断定当前位置是否为三角形数。有两种主要的替代方案：

• (?<=^.)，即我们可以回顾并查看距字符串开头一个点的位置
  • 这在索引1处匹配，是整个过程的关键起点
• 否则，我们测量以重构上次匹配是如何进行的（使用\G作为参考点），将测量结果存储在“before”\G和“after”\G捕获组中。然后，我们检查当前位置是否符合测量要求，以确定下一次匹配应该在哪里进行。

因此，第一种替代方案是微不足道的“基础情况”，而第二种替代方案设置了如何在此之后进行所有后续匹配。Java没有自定义命名组，但以下是3个捕获组的语义：

• \1捕获字符串"before"\G
• \2捕获一些字符串“after”\G
• 如果\1的长度为例如1+2+3+...+k，则\2的长度需要为k。
  • 因此，\2 .的长度为k+1，应该是我们split中的下一个部分！
• \3捕获当前位置右侧的字符串
  • 因此，当我们可以在\1 \G \2 . \3上进行assertEntirety时，我们匹配并设置新的\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 处，则下一个匹配需要在 \G 后面的 k+1 个位置处才能成为三角形数索引。

因此，在我们的示例中，假设在刚刚拆分 def 的位置是 \G，我们测量得到 k=3，下一个匹配将按预期拆分出 ghij。

为了使 \1 和 \2 按照上述规范构建，我们基本上进行了一个 while "循环"：只要它还没有达到 notGyet，我们按以下方式计数到 k：

• +NBefore，即我们通过 forEachDotBehind 扩展了一个 \1
• +1After，即我们只扩展了一个 \2

请注意，notGyet 包含对模式中稍后定义的第1组的 前向引用。本质上，我们循环直到 \1“命中” \G。

---

结论

毫无疑问，这种特定解决方案的性能非常差。正则表达式引擎只记住上一次匹配的位置（使用 \G），而忘记了如何匹配（即所有捕获组在下一次尝试匹配时被重置）。因此，我们的模式必须重新构建匹配方式（传统解决方案中不需要这样做，因为变量不是那么“健忘”），通过逐个字符地追加字符串来费力地构建（这是 O(N^2)）。每个简单的测量都是线性的，而不是恒定时间（因为它是作为一个字符串匹配来完成的，其中长度是一个因素），并且我们进行了许多冗余的测量（即要扩展一个字符，我们需要先重新匹配已有的内容）。

可能有许多“更好”的正则表达式解决方案。尽管如此，这种特定解决方案的复杂性和低效性应该表明正则表达式不是为这种类型的模式匹配而设计的。

话虽如此，出于学习目的，这是一个非常棒的问题，因为研究和制定解决方案的知识丰富。希望这种特定解决方案及其说明是有益的。

- polygenelubricants

Answer 2

正则表达式的目的是识别模式。在这里，你不是在寻找模式，而是在寻找长度分割。因此，正则表达式不合适。

可能有可能通过单个正则表达式实现，但是需要使用以下正则表达式来查找前n个字符：“^(.{n}).*”

因此，你可以使用该正则表达式搜索第一个字符。 然后，你可以进行子字符串操作，并搜索接下来的2个字符。 依此类推。

像@splash所说的那样，这将使代码更加复杂和低效，因为你在使用正则表达式时超出了它们的用途。

- Benoit Courtine

---

“patterns”这个词可以被广泛解释。我的解决方案是一个单一的正则表达式，因此按照这个定义，有一个明确定义的分隔符“模式”。话虽如此，确实使用正则表达式来解决这个任务有些过度，但你可以从中学到很多东西。 - polygenelubricants

Answer 3

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;
        }

    }

- Karl Jamoralin