如何使用Regex使用Python按字母顺序查找字符串？

Question

所以我有一个我正在努力的挑战-找出字符串中最长的字母字符串。例如，“abcghijkyxz”应该产生“ghiijk”（是的，i是加倍的）。在

为了解决这个问题，我已经用循环做了很多工作——迭代整个字符串，然后针对每个字符，使用lower和ord开始第二个循环。没有人需要写那个循环。在

然而，有人向我建议，Regex对这类事情非常有用。我的正则表达式很弱（我知道如何获取静态集，我的前瞻知识扩展到知道它们的存在）。我该如何编写一个正则表达式来向前看，并检查未来字符是否按字母顺序排在下一个？或者使用Regex的建议对这种类型的东西不实用吗？在

编辑：大家普遍认为Regex对于这种类型的东西来说确实很糟糕。在

Answer 1

为了说明为什么regex对这类事情不实用，这里有一个regex，它将匹配给定的abcghiijkyxz示例中的ghiijk。注意，它还将匹配abc、y、x、z，因为技术上应该考虑按顺序排列的最长字母字符串。不幸的是，单独使用regex无法确定哪个最长，但这确实提供了所有的可能性。请注意，这个regex适用于PCRE，不能与python的re模块一起工作！另外，请注意，python's ^{}库当前不支持(*ACCEPT)。虽然我还没有测试，pyre2 package（使用Cython的Google re2pyre2的python包装器）声称它是supports the ^{} control verb，所以现在使用python可以实现这一点。在

See regex in use here

((?:a+(?(?!b)(*ACCEPT))|b+(?(?!c)(*ACCEPT))|c+(?(?!d)(*ACCEPT))|d+(?(?!e)(*ACCEPT))|e+(?(?!f)(*ACCEPT))|f+(?(?!g)(*ACCEPT))|g+(?(?!h)(*ACCEPT))|h+(?(?!i)(*ACCEPT))|i+(?(?!j)(*ACCEPT))|j+(?(?!k)(*ACCEPT))|k+(?(?!l)(*ACCEPT))|l+(?(?!m)(*ACCEPT))|m+(?(?!n)(*ACCEPT))|n+(?(?!o)(*ACCEPT))|o+(?(?!p)(*ACCEPT))|p+(?(?!q)(*ACCEPT))|q+(?(?!r)(*ACCEPT))|r+(?(?!s)(*ACCEPT))|s+(?(?!t)(*ACCEPT))|t+(?(?!u)(*ACCEPT))|u+(?(?!v)(*ACCEPT))|v+(?(?!w)(*ACCEPT))|w+(?(?!x)(*ACCEPT))|x+(?(?!y)(*ACCEPT))|y+(?(?!z)(*ACCEPT))|z+(?(?!$)(*ACCEPT)))+)

结果：

^{pr2}$

单个选项的说明，即a+(?(?!b)(*ACCEPT))：

• a+匹配a（字面意思）一次或多次。这将捕获几个相同字符按顺序排列的实例，例如aa。在
• (?(?!b)(*ACCEPT))If子句计算条件。
  • (?!b)if子句的条件。消极的前瞻性确保下面的内容是不是b。这是因为如果它不是b，我们希望下面的控制动词生效。在
  • (*ACCEPT)如果满足上述条件，我们接受当前的解决方案。此控制谓词导致正则表达式成功结束，跳过模式的其余部分。由于此令牌位于捕获组内，因此只有该捕获组在该特定位置成功结束，而父模式将继续执行。在

那么，如果条件不满足怎么办？好吧，这意味着(?!b)的值为false。这意味着下面的字符实际上是b，因此我们允许匹配（在本例中捕获）继续。请注意，整个模式被包装在(?:)+中，这允许我们匹配连续的选项，直到(*ACCEPT)控制动词或行尾满足为止。在

整个正则表达式的唯一例外是z。因为它是英语字母表中的最后一个字符（我想这是这个问题的目标），所以我们不关心后面是什么，所以我们可以简单地把z+(?(?!$)(*ACCEPT))放进去，这样可以确保z后面没有匹配的内容。相反，如果您想匹配za（如果这是恰当的术语，那么可以使用z+(?(?!a)(*ACCEPT)))+，如果这是正确的术语，那么可以使用z+(?(?!a)(*ACCEPT)))+，如图here。在

Answer 2

如前所述，regex不是最好的工具。由于您对连续序列感兴趣，因此可以使用单个for循环来执行此操作：

def LNDS(s):
    start = 0
    cur_len = 1
    max_len = 1
    for i in range(1,len(s)):
        if ord(s[i]) in (ord(s[i-1]), ord(s[i-1])+1):
            cur_len += 1
        else:
            if cur_len > max_len:
                max_len = cur_len
                start = i - cur_len
            cur_len = 1
    if cur_len > max_len:
        max_len = cur_len
        start = len(s) - cur_len
    return s[start:start+max_len]

>>> LNDS('abcghiijkyxz')
'ghiijk'

我们保持一个运行的总数，我们看到了多少非递减字符，当非递减序列结束时，我们将其与我们之前看到的最长的非递减序列进行比较，如果它更长，则更新我们的“迄今为止最好看的”。在

Answer 3

生成所有regex子字符串，如^a+b+c+$（从最长到最短）。 然后将这些regex与“abcghijkyxz”的所有子字符串（从最长到最短）进行匹配，并在第一个匹配处停止。在

def all_substrings(s):
    n = len(s)
    for i in xrange(n, 0, -1):
        for j in xrange(n - i + 1):
            yield s[j:j + i]

def longest_alphabetical_substring(s):
    for t in all_substrings("abcdefghijklmnopqrstuvwxyz"):
        r = re.compile("^" + "".join(map(lambda x: x + "+", t)) + "$")
        for u in all_substrings(s):
            if r.match(u):
                return u

print longest_alphabetical_substring("abcghiijkyxz")

上面印着“ghiijk”。在