REGEX - 匹配任何重复n次的字符

Question

如何匹配任何重复n次数的角色？

例:

for input: abcdbcdcdd
for n=1:   ..........
for n=2:    .........
for n=3:     .. .....
for n=4:      .  . ..
for n=5:   no matches

几个小时后,我最好的是这个表达

(\w)(?=(?:.*\1){n-1,}) //where n is variable

它使用前瞻性.但是这个表达式的问题是:

for input: abcdbcdcdd
for n=1    .......... 
for n=2     ... .. .
for n=3      ..  .
for n=4       .
for n=5    no matches

正如你所看到的,当前瞻与一个角色匹配时,让我们看看for n=4线条,d前瞻断言是满意的,并且首先d由正则表达式匹配.但剩下d的并不匹配,因为他们没有d比他们还多3个.

我希望我能清楚地说出这个问题.希望您的解决方案,提前感谢.

Answer 1

正则表达式(和有限自动机)不能计入任意整数.它们只能计入预定义的整数,幸运的是这是你的情况.

如果我们首先构造一个非确定性有限自动机(NFA)广告然后将其转换为正则表达式,那么解决这个问题要容易得多.

所以下面的自动机为n = 2,输入字母= {a,b,c,d}

将匹配任何char重复2次的任何字符串.如果没有字符有2次重复(所有字符显示少于或多于两次)字符串将不匹配.

将它转换为正则表达式应该是这样的

"^([^a]*a[^a]*a[^a]*)|([^b]*b[^b]*b[^b]*)|([^b]*c[^c]*c[^C]*)|([^d]*d[^d]*d[^d]*)$"

如果输入字母表很大,这可能会出现问题,因此应该以某种方式缩短正则表达式,但我现在无法想到它.

Answer 2

让我们看一下n = 4行,满意的前瞻断言,并且首先由正则表达式匹配.但剩下的人没有匹配,因为他们之前没有3个以上.

显然,没有正则表达式,这是一个非常简单的字符串操作问题.我正在尝试使用正则表达式进行此操作.

与任何正则表达式实现一样,答案取决于正则表达式的风格.您可以使用.net regex引擎创建解决方案,因为它允许可变宽度的lookbehinds.

另外,我将在下面为perl兼容/类似正则表达式风格提供更通用的解决方案.

.net解决方案

正如@PetSerAl在他的回答中指出的那样,对于可变宽度的lookbehinds,我们可以断言回字符串的开始,并检查是否有n次出现.
ideone demo

Python中的regex模块
你可以使用by Matthew Barnett在python中实现这个解决方案,它也允许可变宽度的lookbehinds.regex module

>>> import regex
>>> regex.findall( r'(\w)(?<=(?=(?>.*?\1){2})\A.*)', 'abcdbcdcdd')
['b', 'c', 'd', 'b', 'c', 'd', 'c', 'd', 'd']
>>> regex.findall( r'(\w)(?<=(?=(?>.*?\1){3})\A.*)', 'abcdbcdcdd')
['c', 'd', 'c', 'd', 'c', 'd', 'd']
>>> regex.findall( r'(\w)(?<=(?=(?>.*?\1){4})\A.*)', 'abcdbcdcdd')
['d', 'd', 'd', 'd']
>>> regex.findall( r'(\w)(?<=(?=(?>.*?\1){5})\A.*)', 'abcdbcdcdd')
[]

广义解

在PCRE或任何"类似Perl的"口味的,有没有解决方案,实际上会返回一个匹配每一个重复的性格,但我们可以创建一个,只有一个,捕捉每一个字符.

战略

对于任何给定的n,逻辑涉及:

1. 早期匹配:匹配并捕获每个字符,然后至少再出现 n个字符.
2. 最终捕获:
   • 匹配并捕获一个字符,然后恰好 n-1次出现,和
   • 还捕获以下每个事件.

例

for n = 3
input = abcdbcdcdd

该角色仅c被M训练一次(作为最终),并且以下2次出现也是同一场比赛中的C:

abcdbcdcdd
  M  C C

而且这个角色d是(早期)M atched一次:

abcdbcdcdd
   M

并且(最后)M再次进行了一次C,其余的是:

abcdbcdcdd
      M CC

正则表达式

/(\w)                        # match 1 character
(?:
    (?=(?:.*?\1){?N?})     # [1] followed by other ?N? occurrences
  |                          #   OR
    (?=                      # [2] followed by:
        (?:(?!\1).)*(\1)     #      2nd occurence <captured>
        (?:(?!\1).)*(\1)     #      3rd occurence <captured>
        ?repeat previous?  #      repeat subpattern (n-1) times
                             #     *exactly (n-1) times*
        (?!.*?\1)            #     not followed by another occurence
    )
)/xg

对于 n =

2. /(\w)(?:(?=(?:.*?\1){2})|(?=(?:(?!\1).)*(\1)(?!.*?\1)))/g
   demo
3. /(\w)(?:(?=(?:.*?\1){3})|(?=(?:(?!\1).)*(\1)(?:(?!\1).)*(\1)(?!.*?\1)))/g
   demo
4. /(\w)(?:(?=(?:.*?\1){4})|(?=(?:(?!\1).)*(\1)(?:(?!\1).)*(\1)(?:(?!\1).)*(\1)(?!.*?\1)))/g
   demo
5. ...等

伪代码生成模式

// Variables: N (int)

character = "(\w)"
early_match = "(?=(?:.*?\1){" + N + "})"

final_match = "(?="
for i = 1; i < N; i++
    final_match += "(?:(?!\1).)*(\1)"
final_match += "(?!.*?\1))"

pattern = character + "(?:" + early_match + "|" + final_match + ")"

JavaScript代码

我将使用javascript显示一个实现,因为我们可以在这里检查结果(如果它在javascript中工作,它适用于任何perl兼容的正则表达式,包括.net,java,python,ruby,perl和所有实现的语言pcre,等等).

var str = 'abcdbcdcdd';
var pattern, re, match, N, i;
var output = "";

// We'll show the results for N = 2, 3 and 4
for (N = 2; N <= 4; N++) {
    // Generate pattern
    pattern = "(\\w)(?:(?=(?:.*?\\1){" + N + "})|(?=";
    for (i = 1; i < N; i++) {
        pattern += "(?:(?!\\1).)*(\\1)";
    }
    pattern += "(?!.*?\\1)))";
    re = new RegExp(pattern, "g");
    
    output += "<h3>N = " + N + "</h3><pre>Pattern: " + pattern + "\nText: " + str;
    
    // Loop all matches
    while ((match = re.exec(str)) !== null) {
        output += "\nPos: " + match.index + "\tMatch:";
        // Loop all captures
        x = 1;
        while (match[x] != null) {
            output += " " + match[x];
            x++;
        }
    }
    
    output += "</pre>";
}

document.write(output);

Python3代码

根据OP的要求,我正在链接到 Python3 implementation in ideone.com