匹配给定字符集幂集中任何内容的正则表达式

Question

我正在编写一个字符串模式匹配算法，我打算用正则表达式来实现它。我希望正则表达式能够匹配给定字符列表的幂集中的任何字符串。

我期望正则表达式以下列方式匹配：

假设我们有一个列表 s = ['a','c','t','a']。

一些匹配的字符串是：

cat, act, tac, at, aa, t, acta, taca, a

同样，一些不匹配的字符串将是：

aaa, tacca, iii, abcd, catk, ab

请记住，字符在集合中出现的次数也被考虑在内。

这也可以表示为上下文无关文法，如果有任何帮助的话

S → A | T | C
A → aT | aC | a | aa | ɛ
T → tA | tC | t | ɛ
C → cA | cT | c | ɛ

Answer 1

这里的一种方法是对字符列表和传入的子字符串进行排序。然后，构建一个由应匹配的单个字母组成的有序正则表达式模式。

s = ['a','c','t','a']
s.sort()
str = ''.join(s)
substring = "at"
substring = '.*'.join(sorted(substring))
print(substring)
if re.match(substring, str):
    print("yes")

a.*t
yes

为了更深入地了解这个解决方案，这里是字符串形式的字符列表，经过排序，后跟所使用的正则表达式模式：

aact
a.*t

因为要匹配的字符串现在已经排序，并且正则表达式的字符是有序的，我们可以简单地通过 .*.

连接字母

Answer 2

我会在没有正则表达式的情况下解决这个问题。使用替换循环很容易完成：

s = ['a','c','t','a']
test_strings = ['cat', 'act', 'tac', 'at', 'aa', 't', 'acta', 'taca', 'a',
                'aaa', 'tacca', 'iii', 'abcd', 'catk', 'ab']

for t in test_strings:
    temp = t
    for c in s:
        temp = temp.replace(c, '', 1)

    if temp == '':
        print('match: ' + t)
    else:
        print('no match: ' + t)

打印：

match: cat
match: act
match: tac
match: at
match: aa
match: t
match: acta
match: taca
match: a
no match: aaa
no match: tacca
no match: iii
no match: abcd
no match: catk
no match: ab

作为函数：

def is_in_powerset(characters, target):
    for c in characters:
        target = target.replace(c, '', 1)
    return target == ''

当然这也可以直接使用字符串：

print(is_in_powerset('acta', 'taa'))

最小化.replace()调用次数的优化版本：

from itertools import groupby

def get_powerset_tester(characters):
    char_groups = [(c, sum(1 for _ in g)) for c, g in groupby(sorted(characters))]
    def tester(target):
        for c, num in char_groups:
            target = target.replace(c, '', num)
        return target == ''
    return tester

tester = get_powerset_tester('acta')
for t in test_strings:
    if tester(t):
        print('match: ' + t)
    else:
        print('no match: ' + t)

Answer 3

看来，如果你逆向搜索，这道题就变得很简单了。包含除 a、c 或 t 之外的任何字符的任何输入都不匹配。

那么除了 aa 我们永远不会看到相同的字符重复出现。但是 aa 只能在 字符串的末尾 .

为了解决 aa 我们可以用单个 a 替换字符串末尾的任何 aa，因为它们在语法上是相同的。

然后我们可以只搜索 aa、cc 和 tt 并在任何匹配项上失败。

import re

test_strings = {
   'cat' : True,
   'act' : True,
   'tac' : True,
   'at' : True,
   'aa' : True,
   't' : True,
   'acta' : True,
   'taca' : True,
   'a' : True,
   'aaa' : False,
   'ataa' : True,
   'aataa' : False,
   'tacca' : False,
   'iii' : False,
   'abcd' : False,
   'catk' : False,
   'ab' : False,
   'catcat' : True,
   'cat' * 40000 : True,
   'actact' : True,
}

for t, v in test_strings.items():
    if not re.search("^[atc]*$", t):
        continue;

    temp = re.sub("aa$", "A", t)
    if re.search("^aa|aA|cc|tt", temp):
        print('no match(%r): %s' % (v, t))
    else:
        print('match(%r): %s' % (v, t))

在上面的代码中，我将 aa 替换为 A，但使用 a 也可以。

或在Ruby

 test_strings = {
   'cat' => true,
   'act' => true,
   'tac' => true,
   'at' => true,
   'aa' => true,
   't' => true,
   'acta' => true,
   'taca' => true,
   'a' => true,
   'aaa' => false,
   'ataa' => true,
   'aataa' => false,
   'tacca' => false,
   'iii' => false,
   'abcd' => false,
   'catk' => false,
   'ab' => false,
   'catcat' => true,
   'cat' * 40000 => true,
   'actact' => true,
}

test_strings.each do |t, v|
    temp = t.dup
    if !temp.match(/^[atc]*$/)
      puts('No match: ' + t + ' ' + temp)
      next;
    end
    temp.sub!(/aa$/, 'A');
    if temp.match(/aA|aa|tt|cc/)
       puts('no match: ' + t[0..80])
       puts "Wrong" if v
    else
       puts('match: ' + t[0..80])
       puts "Wrong" unless v
    end
end

匹配给定字符集幂集中任何内容的正则表达式

Regular expression that matches anything in the powerset of a given set of characters

python

regex

context-free-grammar