주어진 문자열이 전체 문자열에 대해 반복되는지 여부를 테스트하는 방법을 찾고 있습니다.
예 :
[
'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 자 이상이 될 수 있으므로 각 문자를 반복하여 패턴을 작성하려고 시도하고 패턴을 확인하고 나머지 문자열을 확인하는 것은 끔찍한 것처럼 보입니다. 잠재적으로 수백 개의 문자열을 곱하면 직관적 인 솔루션을 볼 수 없습니다.
나는 정규 표현식을 조금 살펴 보았고, 당신이 찾고있는 것을 알거나 적어도 당신이 찾고있는 패턴의 길이를 알 때 좋아 보인다. 불행히도, 나는 둘 다 모른다.
문자열 자체가 반복되는지, 그렇다면 문자열이 가장 짧은 반복 서브 시퀀스인지 어떻게 알 수 있습니까?
답변
다음은 정규 표현식을 피하고 Python 내부 루프를 느리게하는 간결한 솔루션입니다.
def principal_period(s):
i = (s+s).find(s, 1, -1)
return None if i == -1 else s[:i]벤치 마크 결과는 @davidism에서 시작한 Community Wiki 답변을 참조하십시오 . 요약하자면,
David Zhang의 솔루션은 분명한 승자이며, 큰 예제 세트에서 다른 모든 제품보다 5 배 이상 뛰어납니다.
(그것의 대답은 내 것이 아닙니다.)
이것은 문자열 자체가 사소한 회전과 동일한 경우에만 문자열이 주기적이라는 관찰에 기반합니다. sin 의 첫 번째 색인에서 주요 기간을 복구하고 Python의 (s+s)[1:-1]선택적 start및 end인수 를 알려주 는 @AleksiTorhamo에게 Kudos string.find.
답변
다음은 정규 표현식을 사용하는 솔루션입니다.
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()대신 사용을 삭제 하거나 (최소한 2.3까지는 Python에서) 다른 방법으로 이동 re.search()하여 정규식과 함께 사용하면 다른 ^(.+?)\1+$모든 것보다 개인적인 취향에 더 가깝습니다.
답변
문자열이 반복되는 것으로 간주 되려면 길이가 반복되는 시퀀스의 길이로 나눌 수 있어야한다는 것을 알 수 있습니다. 다음은 길이의 제수 1를 n / 2포함 하여 제수를 생성 하고 원래 문자열을 제수의 길이를 가진 하위 문자열로 나누고 결과 집합의 동등성을 테스트 하는 솔루션입니다 .
from math import sqrt, floor
def divquot(n):
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()
def repeats(s):
n = len(s)
for d, q in divquot(n):
sl = s[0:d]
if sl * q == s:
return sl
return None편집 : Python 3에서 /연산자는 기본적으로 부동 나누기를 수행하도록 변경되었습니다. int파이썬 2 에서 나누기 위해 //대신 연산자를 사용할 수 있습니다 . 이 점에 주목 해 주신 @ TigerhawkT3에게 감사합니다.
//모두 파이썬이 파이썬 3 부문의 정수 연산자 수행하는, 그래서 내가 두 버전을 모두 지원하는 대답을 업데이 트했습니다. 모든 하위 문자열이 동일한 지 테스트하기 위해 테스트하는 부분은 이제 all발전기 표현식을 사용한 단락 작업 입니다.
업데이트 : 원래 질문의 변경에 대한 응답으로 코드는 존재하는 경우 가장 작은 반복 하위 문자열을 반환하도록 업데이트되었습니다 None. @godlygeek은 생성기 divmod의 반복 횟수를 줄이는 데 사용 하도록 제안 divisors했으며 코드도 일치하도록 업데이트되었습니다. 이제 모든 양의 제수를 n오름차순으로 반환 n합니다.
고성능을위한 추가 업데이트 : 여러 테스트 후 문자열 동등성 테스트만으로 파이썬의 슬라이싱 또는 반복자 솔루션 중에서 최고의 성능을 발휘한다는 결론에 도달했습니다. 따라서 @ TigerhawkT3의 책에서 나뭇잎을 가져 와서 솔루션을 업데이트했습니다. 이전보다 6 배 이상 빠르며, 특히 Tigerhawk 솔루션보다 빠르지 만 David보다 느립니다.
답변
다음은이 질문에 대한 다양한 답변의 벤치 마크입니다. 테스트되는 문자열에 따라 크게 다른 성능을 포함하여 놀라운 결과가있었습니다.
일부 함수는 Python 3에서 작동하도록 수정되었습니다 (주로 정수 나누기를 보장하기 위해 대체 /하여 //). 뭔가 잘못 보이면 함수를 추가하거나 Python 테스트 룸에서 @ZeroPiraeus를 ping하여 다른 테스트 문자열을 추가하려고합니다 .
요약하자면 여기 에서 OP가 제공 한 대규모 예제 데이터 세트에 대해 최고 성능과 최악 성능의 솔루션간에 약 50 배의 차이가 있습니다 ( 이 의견을 통해 ). David Zhang의 솔루션 은 확실한 승자이며, 큰 예제 세트에서 다른 모든 제품보다 약 5 배 높은 성능을 발휘합니다.
매우 큰 “일치하지 않는”경우에는 몇 가지 답변이 매우 느립니다. 그렇지 않으면 테스트에 따라 기능이 동일하게 일치하거나 확실한 승자 인 것 같습니다.
다음은 다양한 분포를 보여주기 위해 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
코퍼스 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
코퍼스 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
테스트 및 원시 결과는 여기에 있습니다 .
답변
비정규 솔루션 :
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]@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보다 빠르지 않으며 0의 정규식 솔루션은 짧은 문자열보다 우수합니다. 약 1000-1500 문자의 문자열로 (github에 대한 davidism의 테스트에 따르면-그의 대답을 참조하십시오) 가장 빠릅니다. 어쨌든, 테스트 한 모든 경우에서 확실히 두 번째로 빠릅니다 (또는 더 좋습니다). 고마워, 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 부분”인 한 절반으로 줄입니다. 반복 횟수가 짝수 인 경우 검색 공간이 줄어 듭니다. 그런 다음 가장 작은 반복 문자열을 찾기 위해 앞으로 작업하면서 점점 더 큰 하위 문자열로 전체 문자열을 분할하면 빈 값만 나타나는지 확인하십시오. 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가장 짧은 일치를 반환하거나 일치하지 않으면 None을 반환합니다.
답변
O(n)접두사 기능을 사용하면 최악의 경우 에도 문제가 해결 될 수 있습니다 .
참고, 그것은 일반적인 경우에 느 (UPD : 훨씬 느립니다) 할 수의 약수의 개수에 따라 다른 솔루션보다 n하지만, 일반적으로 찾기, 내가 그들에게 나쁜 사례 중 하나가 될 것이라고 생각 빨리 실패 aaa....aab가있는 경우,n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a S ‘
우선 접두사 함수를 계산해야합니다.
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