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

Question

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

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

假设我们有一个列表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']
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 2

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

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 3

似乎如果你搜索反向，这个问题变得非常简单。包含a，c或t之外的任何字符的任何输入都不匹配。

然后除了aa，我们永远不应该看到相同的字符重复。然而，aa只能在一个字符串的末尾。

为了解决aa，我们可以用一个aa替换刺痛结束时的任何a，因为它们在逻辑上都是相同的。

然后我们可以搜索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