所有与正则表达式匹配的重叠子字符串

Question

有没有一个API方法可以返回与正则表达式匹配的所有（可能重叠的）子字符串？

例如，我有一个文本字符串：String t = 04/31 412-555-1235;，我有一个模式：Pattern p = new Pattern("\\d\\d+");，它匹配两个或更多字符的字符串。

我得到的匹配结果是：04, 31, 412, 555, 1235。

如何获取重叠的匹配？

我希望代码返回：04, 31, 41, 412, 12, 55, 555, 55, 12, 123, 1235, 23, 235, 35。

从理论上讲，这应该是可能的 - 有一种明显的O(n^2)算法，可以枚举并检查所有子字符串是否与模式匹配。

与其枚举所有子字符串，不如在Matcher中使用region(int start, int end)方法更安全。对单独提取的子字符串检查模式可能会改变匹配结果（例如，如果模式的开头/结尾有非捕获组或单词边界检查）。

实际上，对于零宽度匹配，region()是否能达到您的预期并不清楚。规范描述模糊不清，实验结果令人失望。

例如：

String line = "xx90xx";
String pat = "\\b90\\b";
System.out.println(Pattern.compile(pat).matcher(line).find()); // prints false
for (int i = 0; i < line.length(); ++i) {
  for (int j = i + 1; j <= line.length(); ++j) {
    Matcher m = Pattern.compile(pat).matcher(line).region(i, j);
    if (m.find() && m.group().size == (j - i)) {
      System.out.println(m.group() + " (" + i + ", " + j + ")"); // prints 90 (2, 4)
    }
  }
}

我不确定最优雅的解决方案是什么。一种方法是在检查pat是否匹配之前，取line的子字符串，并用适当的边界字符填充。

这是我想出的完整解决方案。它可以处理原始正则表达式中的零宽模式、边界等。它遍历文本字符串的所有子字符串，并通过在模式的开头和结尾填充适当数量的通配符来检查正则表达式是否仅在特定位置匹配。根据我尝试的情况，它似乎可以工作 - 尽管我没有进行广泛的测试。它肯定比可能更高效。

  public static void allMatches(String text, String regex)
  {
    for (int i = 0; i < text.length(); ++i) {
      for (int j = i + 1; j <= text.length(); ++j) {
        String positionSpecificPattern = "((?<=^.{"+i+"})("+regex+")(?=.{"+(text.length() - j)+"}$))";
        Matcher m = Pattern.compile(positionSpecificPattern).matcher(text);

        if (m.find()) 
        {   
          System.out.println("Match found: \"" + (m.group()) + "\" at position [" + i + ", " + j + ")");
        }   
      }   
    }   
  }

这是一个更好的做法：https://stackoverflow.com/a/11372670/244526

JRegex库支持查找与Java正则表达式匹配的所有重叠子字符串（尽管似乎有一段时间没有更新了）。具体来说，关于非断开搜索的文档指定：

使用非断开搜索，您可以找到模式的所有可能出现，包括相交或嵌套的出现。这是通过使用Matcher的proceed()方法而不是find()方法实现的。

- dsg

---

只需进行后正则表达式循环遍历所有3个或更多字符的结果。 - You Qi

http://regexlib.com/ 可能是一个好地方进行一些挖掘。 - sathish_at_madison

@Ωmega 我正在尽力，但欢迎提供有用的反馈。干杯。 - sathish_at_madison

我认为正则表达式不会进行重复扫描。在一个大字符串中，一个字符只能被匹配一次。我所能想到的最接近的方法是使用非贪婪模式匹配，但这只能返回12和35，无法得到1235。 - You Qi

重复：https://dev59.com/3VrUa4cB1Zd3GeqPpP1r?rq=1 - dsg

Answer 1

我遇到了类似的情况，尝试了上面的答案，但在我的情况下，通过设置匹配器的开始和结束索引花费了太多时间，但我认为我已经找到了更好的解决方案，我在这里发布它供其他人参考。所以以下是我的代码片段。

if (textToParse != null) {
Matcher matcher = PLACEHOLDER_PATTERN.matcher(textToParse);
    while(matcher.hitEnd()!=true){
        Boolean result = matcher.find();
        int count = matcher.groupCount();
        System.out.println("Result " +result+" count "+count);
        if(result==true && count==1){
            mergeFieldName = matcher.group(1);
            mergeFieldNames.add(mergeFieldName);
           }
       }
  }

我已经使用matcher.hitEnd()方法来检查是否到达了文本末尾。

希望这可以帮到你。 谢谢！

- Darshan

Answer 2

你能得到的最接近的东西就是这样。

"(?=((\\d*)\\d))(?=(\\d)\\d*)"

结果将在捕获组1、2和3中。

就我所知，只有在零长度断言中捕获文本才是重新捕获字符串相同位置的可行方法。在零长度断言之外捕获文本将一次性消耗文本（Java中的后顾断言只能捕获固定长度，因此可以认为它是不可访问的）。

这个解决方案并不完美：除了重复（在相同位置的文本！）和空字符串匹配之外，它无法捕获所有可能的子字符串。

捕获所有可能的子字符串的一种方法是使用从1开始的n值构造以下正则表达式：

"(?=(\\d{" + n + "}))"

将字符串与此进行匹配，以增加n的值，直到没有匹配项为止。

当然，与使用"\d+"匹配所有数字并提取所有子字符串的方法相比，这种方法效率较低。

- nhahtdh

Answer 3

只有在指定允许的数字长度范围时才能实现O(n)。

比如说从2到4位数（数字00-9999）：(?=(\\d{2}))(?=(\\1\\d)?)(?=(\\2\\d)?)

这是通过正向前瞻的零长度断言，将其捕获到组中。结果是一个包含在正则表达式输入中找到的所有2到4位数字字符串的数组，包括重复和空字符串（对于非匹配捕获）。

我不是Java开发人员，但我相信Perl脚本也可以作为示例阅读。

#!/usr/bin/perl                                       # perl script
use List::MoreUtils qw/ uniq /;                       # uniq subroutine library
$_ = '04/31 412-555-1235';                            # input
my @n = uniq (/(?=(\d{2}))(?=(\1\d)?)(?=(\2\d)?)/g);  # regex (single slash in Perl)
print "$_\n" for grep(/\S/, @n);                      # print non-empty lines

技巧是使用反向引用。如果您想捕获2-5位数字字符串，则需要在正则表达式中使用一个以上的正向先行断言：(?=(\\d{2}))(?=(\\1\\d)?)(?=(\\2\\d)?)(?=(\\3\\d)?)。

我相信这是您可以做到的最接近方法。如果这对您有用，请留下评论，希望一些Java开发人员将用Java代码编辑上述脚本。

- Ωmega

---

正则表达式在Java中是相同的（除了反斜杠需要转义）。至于uniq，在Java中可以用Set来模拟（使用TreeSet或HashSet）。 - nhahtdh

@nhahtdh - 谢谢。请随意通过编辑帖子来更新我的答案。 - Ωmega