所有匹配java正则表达式的重叠子串

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）算法，它根据模式枚举并检查所有子字符串。

编辑

使用匹配器中的区域（int start，int end）方法比枚举所有子字符串更安全。根据单独提取的子字符串检查模式可能会更改匹配结果（例如，如果在模式的开始/结束处存在非捕获组或单词边界检查）。

编辑2

实际上，还不清楚区域（）是否满足零宽度匹配的要求。规范是模糊的，实验结果令人失望。

例如：

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的子字符串，并用适当的边界字符填充。

编辑3

以下是我提出的完整解决方案。它可以在原始正则表达式中处理零宽度模式、边界等。它检查文本字符串的所有子字符串，并通过在模式的开头和结尾填充适当数量的通配符来检查正则表达式是否仅在特定位置匹配。它似乎适用于我尝试过的案例——尽管我还没有做过广泛的测试。毫无疑问，它的效率比它可能的要低。

  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 + ")");
        }   
      }   
    }   
  }

编辑4

这里有一个更好的方法：https://stackoverflow.com/a/11372670/244526

编辑5

JRegex库支持查找与java正则表达式匹配的所有重叠子字符串（尽管它似乎暂时没有更新）。具体而言，关于非破坏性搜索的文档规定：

使用非中断搜索，您可以找到一个模式的所有可能发生的情况，包括那些相交或嵌套的情况。这是通过使用Matcher的方法procedure（）而不是find（）实现的




Answer 1

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

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

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

就我的想象而言，我只能认为在零长度断言中捕获是重新获取字符串相同位置的可行方法。捕获零长度断言之外的文本将一次性使用文本（look behind在Java中只能捕获固定长度的文本，因此可以认为它不可访问）。

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

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

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

并将字符串与之匹配，以增加n的值，直到没有匹配为止。

当然，与用“\d”匹配所有数字并提取所有子串的方法相比，这种方法效率低下。

Answer 2

只有在指定允许的数字长度范围时，它才可以作为O（n）。

假设从2-4位数字（数字00-9999）：（？=（\\d{2}））（？=（\\1\\d）？）（？=（\\2\\d）？）

这是一个通过正向前瞻的零长度断言，将此类前瞻捕获到组中。结果是在regex输入中可以找到的所有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代码编辑我的答案。

Answer 3

我遇到了类似的情况，我尝试了上述答案，但在我的情况下，设置匹配器的开始和结束索引花费了太多时间，但我认为我找到了一个更好的解决方案，我在这里发布给其他人。下面是我的代码剪。

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

我用过火柴。方法来检查我是否已到达文本的末尾。

希望这有帮助。谢谢