我如何知道一个字符串在Python中重复自己?

我正在寻找一种方法来测试一个给定的字符串是否在整个字符串中重复自己。

例子:

[
    '0045662100456621004566210045662100456621',             # '00456621'
    '0072992700729927007299270072992700729927',             # '00729927'
    '001443001443001443001443001443001443001443',           # '001443'
    '037037037037037037037037037037037037037037037',        # '037'
    '047619047619047619047619047619047619047619',           # '047619'
    '002457002457002457002457002457002457002457',           # '002457'
    '001221001221001221001221001221001221001221',           # '001221'
    '001230012300123001230012300123001230012300123',        # '00123'
    '0013947001394700139470013947001394700139470013947',    # '0013947'
    '001001001001001001001001001001001001001001001001001',  # '001'
    '001406469760900140646976090014064697609',              # '0014064697609'
]

是重复自己的字符串，和

[
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

是一些不这样做的例子。

我给出的字符串的重复部分可能相当长，字符串本身可能有500个或更多字符，因此循环每个字符试图构建一个模式，然后检查模式与字符串的其余部分似乎非常慢。再乘以几百个字符串，我看不出任何直观的解决方案。

我研究了一下正则表达式，当你知道你在寻找什么，或者至少知道你在寻找的模式的长度时，它们似乎很有用。不幸的是，我两个都不知道。

我怎么知道一个字符串是否在重复它自己，如果是的话，最短的重复子序列是什么?

当前回答

这里有一个使用正则表达式的解决方案。

import re

REPEATER = re.compile(r"(.+?)\1+$")

def repeated(s):
    match = REPEATER.match(s)
    return match.group(1) if match else None

遍历问题中的例子:

examples = [
    '0045662100456621004566210045662100456621',
    '0072992700729927007299270072992700729927',
    '001443001443001443001443001443001443001443',
    '037037037037037037037037037037037037037037037',
    '047619047619047619047619047619047619047619',
    '002457002457002457002457002457002457002457',
    '001221001221001221001221001221001221001221',
    '001230012300123001230012300123001230012300123',
    '0013947001394700139470013947001394700139470013947',
    '001001001001001001001001001001001001001001001001001',
    '001406469760900140646976090014064697609',
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

for e in examples:
    sub = repeated(e)
    if sub:
        print("%r: %r" % (e, sub))
    else:
        print("%r does not repeat." % e)

．.．产生如下输出:

'0045662100456621004566210045662100456621': '00456621'
'0072992700729927007299270072992700729927': '00729927'
'001443001443001443001443001443001443001443': '001443'
'037037037037037037037037037037037037037037037': '037'
'047619047619047619047619047619047619047619': '047619'
'002457002457002457002457002457002457002457': '002457'
'001221001221001221001221001221001221001221': '001221'
'001230012300123001230012300123001230012300123': '00123'
'0013947001394700139470013947001394700139470013947': '0013947'
'001001001001001001001001001001001001001001001001001': '001'
'001406469760900140646976090014064697609': '0014064697609'
'004608294930875576036866359447' does not repeat.
'00469483568075117370892018779342723' does not repeat.
'004739336492890995260663507109' does not repeat.
'001508295625942684766214177978883861236802413273' does not repeat.
'007518796992481203' does not repeat.
'0071942446043165467625899280575539568345323741' does not repeat.
'0434782608695652173913' does not repeat.
'0344827586206896551724137931' does not repeat.
'002481389578163771712158808933' does not repeat.
'002932551319648093841642228739' does not repeat.
'0035587188612099644128113879' does not repeat.
'003484320557491289198606271777' does not repeat.
'00115074798619102416570771' does not repeat.

正则表达式(.+?)\1+$分为三部分:

(.+?)是一个匹配组，包含至少一个(但尽可能少)任意字符(因为+?是贪婪的,)。 \1+检查第一部分中匹配组是否至少重复一次。 $检查字符串的结尾，以确保在重复的子字符串之后没有额外的非重复内容(并且使用re.match()确保在重复的子字符串之前没有非重复文本)。

在Python 3.4及以后版本中，你可以放弃$而使用re.fullmatch()，或者(至少在任何Python 2.3版本中)使用re.search()和正则表达式^(.+?)\1+$，所有这些都取决于个人的喜好。

2015-04-06 23:18:16

其他回答

首先，将字符串减半，只要它是“2部分”副本。如果重复次数为偶数，这将减少搜索空间。然后，向前查找最小的重复字符串，检查将整个字符串拆分为越来越大的子字符串是否只得到空值。只有长度不超过// 2的子字符串需要测试，因为超过这个长度的任何子字符串都没有重复。

def shortest_repeat(orig_value):
    if not orig_value:
        return None

    value = orig_value

    while True:
        len_half = len(value) // 2
        first_half = value[:len_half]

        if first_half != value[len_half:]:
            break

        value = first_half

    len_value = len(value)
    split = value.split

    for i in (i for i in range(1, len_value // 2) if len_value % i == 0):
        if not any(split(value[:i])):
            return value[:i]

    return value if value != orig_value else None

这将返回最短的匹配，如果没有匹配则返回None。

2015-04-07 02:42:00

这个版本只尝试那些候选序列长度，是字符串长度的因素;并使用*操作符从候选序列构建一个完整的字符串:

def get_shortest_repeat(string):
    length = len(string)
    for i in range(1, length // 2 + 1):
        if length % i:  # skip non-factors early
            continue

        candidate = string[:i]
        if string == candidate * (length // i):
            return candidate

    return None

感谢TigerhawkT3注意到长度// 2没有+ 1将无法匹配abab情况。

2015-04-07 06:13:35

下面是一个简洁的解决方案，它避免了正则表达式和缓慢的python循环:

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

请参阅由@davidism开始的社区Wiki回答以获得基准测试结果。总之,

David Zhang的解决方案显然是赢家，在大型示例集中，它的表现至少比其他所有解决方案好5倍。

(这是我的原话，不是我的。)

这是基于这样的观察:当且仅当字符串等于自身的非平凡旋转时，它是周期性的。感谢@AleksiTorhamo实现了从(s+s)[1:-1]中第一次出现的s的索引中恢复主周期，并通知我Python的string.find的可选开始和结束参数。

2015-04-07 10:58:10

在David Zhang的回答中，如果我们有某种循环缓冲区，这将不起作用:principal_period('6210045662100456621004566210045662100456621')由于开始621，在那里我希望它吐出:00456621。

扩展他的解决方案，我们可以使用以下方法:

def principal_period(s):
    for j in range(int(len(s)/2)):
        idx = (s[j:]+s[j:]).find(s[j:], 1, -1)
        if idx != -1:
            # Make sure that the first substring is part of pattern
            if s[:j] == s[j:][:idx][-j:]:
                break

    return None if idx == -1 else s[j:][:idx]

principal_period('6210045662100456621004566210045662100456621')
>>> '00456621'

2016-12-23 01:30:52