string - 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或者多个字符,所以该模式 vs 逐个遍历所有字符在尝试创建一个模型然后检查剩下的字符串看起来令人敬畏的慢了。 乘以可能数以百计的字符串,我无法看到任何直观的解决方案。

我研究过regex有点和他们看起来很适合当你知道你要找的,或者至少你要查找的模式的长度。 不幸的是,我都知道。

如何才能判断一个字符串是否是重复本身和如果是,又最短的重复子序列是什么?

时间:

下面是一个简洁的解决方案,它避免了 正规表达式 和慢速in-Python循环:


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

于基准测试results,查看相关鼠标开始社区维基回答 总之

至少 5 x 针对大型示例set,大卫解决方案的张先生是明显胜出,超出所有其他人 by.

( 答案,不是我的)

这是基于观察一个字符串是周期性的,如果它等于一个非平凡旋转。 @AleksiTorhamo的荣誉,我们可以从 (s+s)[1:-1] 第一次出现的s的索引中恢复主句点,并告诉我 python的可选 startend 参数。

这是一个使用 正规表达式的解决方案。


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. 至少一个任意字符的( 但是尽可能少的) containing. (.+?) 是一个匹配组

  2. 1+ 在第一部分检查匹配组的至少一个重复。

  3. 之后的重复子串 $ 检查是否存在字符串的结尾,以确保没有任何额外费用,non-repeating content.

在 python 3.4及更高版本,你可以掉 $ 而使用 re.fullmatch() 派生,或者( 在任何 python 中,至少在 2.3的时候) 朝另一个方向走,使用 re.search() 与 正规表达式 ^(.+?)1+$,所有这些都是比别的更取决于个人的感觉。

你可以让观察字符串被认为重复,它的长度必须被重复序列的长度整除。 给出了一个解决方案,它生成从 1n/2的长度的除数,将原始字符串除以除数的长度,并测试结果集的相等性:


def repeats(s):

 def divquot(n):
 from math import sqrt, floor
 if n> 1:
 yield 1, n
 swapped = []
 for d in range(2, int(floor(sqrt(n))) + 1):
 q, r = divmod(n, d)
 if r == 0:
 yield d, q
 swapped.append((q, d))
 while swapped:
 yield swapped.pop()

 n = len(s)
 for d, q in divquot(n):
 sl = s[0:d]
 if sl * q == s:
 return sl
 return None

python 中编辑: 3,则默认情况下已经更改为 / 运算符做浮点除法。 要从它的获取 int 除法 python 2,你可以使用 // 运算符代替。 感谢 @TigerhawkT3 给我带来的注意。

// 运算符在 python 2和 python 3中执行整数除法,因此我更新了支持两个版本的答案。 我们测试所有子字符串是否相等的部分现在是一个short-circuiting操作,它使用 all 和生成器表达式。

更新原来: 在响应查询的变化问题,代码现在已经被更改为返回最小的重复子串,如果该文件存在并且 None ;如果没有,就 @godlygeek 建议使用 divmod 来减少 divisors 生成器上的迭代次数,并且代码已经被更新以匹配同样的情况。 它现在以升序返回所有 n的正整数,而非 n 本身。

高性能的进一步更新: 在多个测试后,我已经总结点数,它只是测试对于字符串相等有任何Fragment或者迭代器的性能达到最佳解决办法, 因此,我从 @TigerhawkT3 图书中取出了一片叶子,更新了我的解决方案。 现在的速度超过了 6 x,速度比tigerhawk快,但比慢。

下面是这个问题的各种答案的基准。 有一些令人吃惊的结果,包括根据正在测试的字符串的不同,性能非常不同。

一些函数被修改为使用 python 3 ( 主要通过将 / 替换为 // 来确保整数除法) 。 在 , python 聊天室如果你看出什么问题了,想添加你的职责,或者想添加另一个测试字符串,平

总的来说:在best-和worst-performing解决方案之间有一个 50 x的差异,由 OP 提供的大量示例数据在这里是 ( 通过这里注释) 。 于大相关示例 set, 大卫解决方案由 5周围的张是明显胜出,超出所有其他x 。

在非常大的"没有匹配"cases,一对夫妇的答案都不非常慢了, 否则,根据测试的不同,函数似乎相等或者明显的赢家。

以下是结果,包括使用matplotlib和seaborn来显示不同发行版的绘图:


语料 1 ( 提供的示例- 小集合)


mean performance:
 0.0003 david_zhang
 0.0009 zero
 0.0013 antti
 0.0013 tigerhawk_2
 0.0015 carpetpython
 0.0029 tigerhawk_1
 0.0031 davidism
 0.0035 saksham
 0.0046 shashank
 0.0052 riad
 0.0056 piotr

median performance:
 0.0003 david_zhang
 0.0008 zero
 0.0013 antti
 0.0013 tigerhawk_2
 0.0014 carpetpython
 0.0027 tigerhawk_1
 0.0031 davidism
 0.0038 saksham
 0.0044 shashank
 0.0054 riad
 0.0058 piotr

Corpus 1 graph


语料 2 ( 提供的示例- 大集合)


mean performance:
 0.0006 david_zhang
 0.0036 tigerhawk_2
 0.0036 antti
 0.0037 zero
 0.0039 carpetpython
 0.0052 shashank
 0.0056 piotr
 0.0066 davidism
 0.0120 tigerhawk_1
 0.0177 riad
 0.0283 saksham

median performance:
 0.0004 david_zhang
 0.0018 zero
 0.0022 tigerhawk_2
 0.0022 antti
 0.0024 carpetpython
 0.0043 davidism
 0.0049 shashank
 0.0055 piotr
 0.0061 tigerhawk_1
 0.0077 riad
 0.0109 saksham

Corpus 1 graph


语料 3 ( 边缘案例)


mean performance:
 0.0123 shashank
 0.0375 david_zhang
 0.0376 piotr
 0.0394 carpetpython
 0.0479 antti
 0.0488 tigerhawk_2
 0.2269 tigerhawk_1
 0.2336 davidism
 0.7239 saksham
 3.6265 zero
 6.0111 riad

median performance:
 0.0107 tigerhawk_2
 0.0108 antti
 0.0109 carpetpython
 0.0135 david_zhang
 0.0137 tigerhawk_1
 0.0150 shashank
 0.0229 saksham
 0.0255 piotr
 0.0721 davidism
 0.1080 zero
 1.8539 riad

Corpus 3 graph


这里的测试和来自映射的原始结果是可用

Non-regex解决方案:


def repeat(string):
 for i in range(1, len(string)//2+1):
 if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string:
 return string[0:i]

更快的non-regex解决方案,感谢 @ThatWeirdo ( 查看评论):


def repeat(string):
 l = len(string)
 for i in range(1, len(string)//2+1):
 if l%i: continue
 s = string[0:i]
 if s*(l//i) == string:
 return s

上面的解决方案很少比原始的慢一些,但它通常是一个较快的速度,有时会更快。 它仍然不是速度比为davidism的长字符串和短字符串的指数型 正规表达式 。优于。 它出现在最快的( 根据github上的davidism测试- 查看他的答案) 中,字符串约为 1000个字符。 无论如何,它在所有情况下都是可靠的second-fastest ( 或者更好或者更好) 。 谢谢,ThatWeirdo 。

测试:


print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))

结果:


009
2547
abcde
None
None
None

首先,只要字符串是" 2部分"重复,就减半。 这减少了搜索空间如果有偶数重复。 然后,向前工作查找最小的重复字符串,检查是否通过越来越大的sub-string来分割完整的字符串,结果只有空值。 只需要测试sub-strings到 length//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

如果没有匹配项,则返回最短匹配或者无。

这里版本只尝试那些作为 string length; 因子的候选序列长度,并使用 * 运算符从候选序列构建一个full-length字符串:


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注意到 length//2 没有 + 1 将无法与 abab 大小写匹配。

这是一个直接的正向解决方案,没有正则表达式。

对于 s 从零索引开始的子字符串,长度为 1到 len(s),检查子字符串是否为重复模式。 这个检查可以通过将 substr 与其自身的ratio 时间连接起来,这样形成的字符串的长度等于 s的长度。 因此 ratio=len(s)/len(substr)

当找到第一个此类子字符串时返回。 如果存在的话,这将提供最小的子字符串。


def check_repeat(s):
 for i in range(1, len(s)):
 substr = s[:i]
 ratio = len(s)/len(substr)
 if substr * ratio == s:
 print 'Repeating on"%s"' % substr
 return
 print 'Non repeating'

>>> check_repeat('254725472547')
Repeating on"2547"
>>> check_repeat('abcdeabcdeabcdeabcde')
Repeating on"abcde"

问题也可以在 O(n) 中解决,在最糟糕的情况下带有前缀函数。

注意,一般情况下可能较慢( 更新: 于他们将被 aaa....aab 相关,其本are,和比其他的解决方案是慢很多) 这取决于多种分区的n,但往往觉得失败不久,我认为上一个不好的情况 n - 1 = 2 * 3 * 5 * 7.. . *p_n - 1a

首先,你需要计算前缀函数


def prefix_function(s):
 n = len(s)
 pi = [0] * n
 for i in xrange(1, n):
 j = pi[i - 1]
 while(j> 0 and s[i]!= s[j]):
 j = pi[j - 1]
 if (s[i] == s[j]):
 j += 1
 pi[i] = j;
 return pi

要么没有答案,要么是最短的时间


k = len(s) - prefix_function(s[-1])

你只要检查一下 k!= n and n % k == 0 ( 如果 k!= n and n % k == 0 那么答案是 s[:k],否则没有答案

你可以在这里检查校样 ( 在俄语中,但在线翻译可能会这样做)


def riad(s):
 n = len(s)
 pi = [0] * n
 for i in xrange(1, n):
 j = pi[i - 1]
 while(j> 0 and s[i]!= s[j]):
 j = pi[j - 1]
 if (s[i] == s[j]):
 j += 1
 pi[i] = j;
 k = n - pi[-1]
 return s[:k] if (n!= k and n % k == 0) else None

我开始了这个问题的八个上解决方案。 一些基于 正规表达式 ( 匹配,findall,拆分),一些是字符串切片和测试,有些是使用字符串方法( 查找,计数,拆分) 。 在代码清晰度,代码大小,速度和内存消耗方面都有好处。 我将在这里发表我的回答,当我注意到执行速度被列为重要的时候,所以我做了更多的测试和改进来达到这一点:


def repeating(s):
 size = len(s)
 incr = size % 2 + 1
 for n in xrange(1, size//2+1, incr):
 if size % n == 0:
 if s[:n] * (size//n) == s:
 return s[:n]

这里答案类似于其他一些答案,但它有一些速度优化,其他的没有使用:

  • xrange 在这个应用程序中稍微快一点,
  • 如果输入字符串为奇数长度,则不检查任何长度子字符串,
  • 通过直接使用 s[:n],我们避免在每个循环中创建变量。

我很想看看这是如何在普通硬件的标准测试中执行的。 我相信它还是很好地避免大卫出色的张算法在大多数测试,但应该相当快速的以其他方式。

我发现这个问题非常 counter-intuitive 。 我认为速度很快的解决方案。 看起来缓慢的解决方案是快速的 ! 看起来使用乘法运算符和字符串比较的python 创建是高度优化的。

...