如何基于给定的正则表达式获取所有子字符串？

Question

我需要获取所有与正则表达式匹配的子字符串，我知道我可能可以为此构建一个自动机，但我正在寻找一个更简单的解决方案。
问题在于，Matcher.find()并不能返回所有结果。

String str = "abaca";
Matcher matcher = Pattern.compile("a.a").matcher(str);
while (matcher.find()) {
   System.out.println(str.substring(matcher.start(),matcher.end()));
}

结果是aba而不是我想要的aba,aca...
有什么想法吗？
编辑： 另一个例子：对于字符串=abaa，正则表达式=a.*a，我希望得到aba、abaa、aa。
附言：如果无法使用正则表达式实现，这也是一种答案，我只想知道我是否正在为语言已经提供给我的东西重复造轮子...

- amit

---

我曾经遇到过同样的问题，看这里：https://dev59.com/XVXTa4cB1Zd3GeqPxgFS - Dmitrij Golubev

问题在于匹配器只考虑不重叠的匹配。尽管如此，这仍然是一个有趣的问题。+1 - Konrad Rudolph

Answer 1

你可以像这样做：

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    public static List<String> getAllMatches(String text, String regex) {
        List<String> matches = new ArrayList<String>();
        Matcher m = Pattern.compile("(?=(" + regex + "))").matcher(text);
        while(m.find()) {
            matches.add(m.group(1));
        }
        return matches;
    }

    public static void main(String[] args) {
        System.out.println(getAllMatches("abaca", "a.a"));
        System.out.println(getAllMatches("abaa", "a.*a"));
    }
}

它会打印：

[aba, aca]
[abaa, aa]

唯一的问题是你在最后的匹配列表中缺少了aba。这是因为a.*a中的贪婪.*。你无法用正则表达式解决这个问题。你可以通过迭代所有可能的子字符串并在每个子字符串上调用.matches(regex)来解决这个问题：

public static List<String> getAllMatches(String text, String regex) {
    List<String> matches = new ArrayList<String>();
    for(int length = 1; length <= text.length(); length++) {
        for(int index = 0; index <= text.length()-length; index++) {
            String sub = text.substring(index, index + length);
            if(sub.matches(regex)) {
                matches.add(sub);
            }
        }
    }
    return matches;
}

如果您的文本规模较小，那么这将起作用，但对于较大的字符串来说，这可能会变得过于计算密集。

- Bart Kiers

---

这正是我想知道是否有一个简单的正则表达式解决方案的问题。 - amit

不，仅使用正则表达式没有简单的方法。请注意，这并不是您的整个问题：您的第一个问题是由于“重叠命中”，导致您无法获得多个匹配项，而我的建议解决了这个问题（我也要感谢 Dmitrij Golubev）。 - Bart Kiers

Answer 2

默认情况下，新匹配从上一个匹配的结尾开始。如果您的匹配可以重叠，则需要手动指定起始点：

int start = 0;
while (matcher.find(start)) { 
    ...
    start = matcher.start() + 1;
}

- axtavt

---

如果我有字符串=abaa和正则表达式=a.*a，仍然不足以获取所有结果，只能得到一个结果。 - amit

@amit：你上面的例子（字符串=abaa，正则表达式=a.*a）的预期输出是什么？ - NPE

@aix：aba，abaa，aa……当然，问题不仅仅局限于这些简单的例子，这只是其中一个建议解决方案失败的点。 - amit

@amit：不过，你可能想把这个例子加到问题中，因为它展示了一个并非从问题中显而易见的你的期望方面。 - NPE

Answer 3

这是一种计算上开放的问题。所有正则表达式可能匹配的问题可以重新表述为

What are all the possible sub strings of a given String that match the given regex?

所以你的代码真正需要做的是（伪代码）：

for(String substring: allPossibleSubstrings) {
    if(PATTERN.matches(subString) {
        results.add(subString);
    }
}

现在对于像abaa这样的字符串，这是微不足道的：AllPossible = ["a", "ab", "aba", "abaa", "ba", "baa", "aa"] 您还可以通过限制子字符串的大小来添加一些智能，以便与正则表达式匹配的最小大小。当然，对于大字符串，这将呈指数级扩展。

- Java Drinker

Answer 4

在你的while循环中使用matcher.find(startingFrom)，并将startingFrom增加到上一个匹配的起始位置加1：startingFrom = matcher.start()+1;

- Rikki

---

这正是@axtavt建议的，然而在这个问题中不够用，详见编辑后的问题（最后一个例子）。 - amit

@amit，我发布后才看到@axtavt的回答（及随后的讨论）。 - Rikki

@Rikki：在这种情况下,请删除答案会很受欢迎。 - amit

@amit 哎呀，我不小心按了回车键！在我的代码测试中，"abaa" =~ m/a.*a/，结果为("abaa", "aa")：所以我得到了不止一个结果，但不是你想要的全部三个。这是由于正则表达式的贪婪/懒惰性。a.a会吃掉它能吃掉的所有字符串。而用 a.?a 代替它（使其变成懒惰模式），将会给你 ("aba", "aa")。我希望像 (a.*?a)|(a.*a) 这样的东西能够奏效，但事实并非如此，所以你必须为两个正则表达式都匹配字符串：a.a 和 a.?a，然后消除重复结果。 - Rikki

@amit 好的，我现在明白了。这在原始帖子中一点也不清楚。我认为你的例子需要更少的具体性，或者包括更多的迭代（例如使用aba、abaa、abaaa、abaaaa作为例子）。不，我认为这是无法通过正则表达式实现的。你只能懒惰或贪婪，而不能两者兼备。 - Rikki

@amit ...除了使用regex = "a.{"+n+"}a";并在增加n的同时循环之外，没有其他方法。当然，这仅在您有一个上限（您可能在匹配的字符串长度中有）时才可行。 - Rikki