2

我有一组 n 个令牌（例如，a、b、c）分布在一堆其他令牌中。我想知道我的集合中的所有成员是否都出现在给定数量的位置（窗口大小）内。我突然想到，也许可以编写一个 RegEx 来捕获这种状态，但我不知道确切的语法。

          11111
012345678901234
ab ab bc a cba

在这个例子中，给定窗口大小=5，我想cba在位置 12-14 和abc位置 3-7 匹配。

有没有办法用正则表达式来做到这一点，或者有没有其他类型的语法可以用来捕捉这个逻辑？

我希望在 Java 中实现这一点。

4

4 回答 4

2

这是一个匹配包含所有“a”、“b”和“c”的 5 个字母序列的正则表达式：

(?=.{0,4}a)(?=.{0,4}b)(?=.{0,4}c).{5}

因此，虽然基本上匹配任何 5 个字符（带有.{5}），但匹配必须遵守三个先决条件。它们中的每一个都需要存在一个标记/字母（最多 4 个字符，后跟“a”等）。(?=X)匹配“X，零宽度正向预读”，其中零宽度表示匹配时不移动字符位置。

但是，使用正则表达式执行此操作很慢。这是一个更直接的版本（似乎比使用正则表达式快 15 倍）：

public static void find(String haystack, String tokens, int windowLen) {
    char[] tokenChars = tokens.toCharArray();
    int hayLen = haystack.length();

    int pos = 0;
    nextPos:
    while (pos + windowLen <= hayLen) {
        for (char c : tokenChars) {
            int i = haystack.indexOf(c, pos);
            if (i < 0) return;

            if (i - pos >= windowLen) {
                pos = i - windowLen + 1;
                continue nextPos;
            }
        }

        // match found at pos
        System.out.println(pos + ".." + (pos + windowLen - 1) + ": " + haystack.substring(pos, pos + windowLen));
        pos++;
    }
}
于 2011-04-30T01:18:03.390 回答
2

这个经过测试的 Java 程序有一个注释的正则表达式，它可以解决问题：

import java.util.regex.*;
public class TEST {
    public static void main(String[] args) {
        String s = "ab ab bc  a cba";
        Pattern p = Pattern.compile(
            "# Match 5 char sequences containing: a and b and c\n" +
            "(?=[abc])     # Assert first char is a, b or c.\n" +
            "(?=.{0,4}a)   # Assert an 'a' within 5 chars.\n" +
            "(?=.{0,4}b)   # Assert an 'b' within 5 chars.\n" +
            "(?=.{0,4}c)   # Assert an 'c' within 5 chars.\n" +
            ".{5}          # If so, match the 5 chers.", 
            Pattern.COMMENTS);
        Matcher m = p.matcher(s);
        while (m.find()) {
            System.out.print("Match = \""+ m.group() +"\"\n");
        } 
   }
}

S9:13" a cb"请注意，您的测试数据中还有另一个有效序列（在 . 之前，S12:14"cba"假设您不想匹配这个，我添加了一个额外的约束来将其过滤掉，这要求 5 字符窗口必须以a,b或c.

这是脚本的输出：

Match = "ab bc"
Match = "a cba"

于 2011-04-30T04:14:13.830 回答
1

好吧，一种可能性（尽管完全不切实际）是简单地匹配所有排列：

abc..|ab.c.|ab..c| .... etc.

这可以在某种程度上分解：

ab(c..|.c.|..c)|a.(bc.|b.c .... etc.

我不确定您是否可以使用正则表达式做得更好。

于 2011-04-30T00:14:24.207 回答
0 
Pattern p = Pattern.compile("(?:a()|b()|c()|.){5}\\1\\2\\3");
String s = "ab ab bc  a cba";
Matcher m = p.matcher(s);
while (m.find())
{
  System.out.println(m.group());
}

输出：

ab bc
 a cb

这是受到正则表达式食谱中的配方 #5.7 的启发。每个反向引用 ( \1, \2, \3) 就像一个零宽度断言，表明相应的捕获组参与了匹配，即使该组本身没有消耗任何字符。

作者警告说，这个技巧依赖于大多数风格中未记录的行为。它适用于 Java、.NET、Perl、PHP、Python 和 Ruby（原始和 Oniguruma），但不适用于 JavaScript 或 ActionScript。

于 2011-04-30T08:27:31.147 回答