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자 이상일 수 있습니다.따라서 패턴을 작성하려고 한 후 패턴을 확인하려고 하면 나머지 문자열의 반복은 매우 느립니다.여기에 수백 개의 문자열을 곱하면 직관적인 해결책이 보이지 않습니다.
정규식에 대해 조금 알아봤는데 원하는 것 또는 최소한 원하는 패턴의 길이를 알 수 있을 때 적합합니다.아쉽게도 저도 몰라요.
문자열이 반복 중인지, 반복 중이면 가장 짧은 반복 시퀀스가 무엇인지 어떻게 알 수 있습니까?
다음은 정규 표현과 느린 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배 이상 우수합니다.
(그 대답은 내 말이 아니라)
이는 문자열 자체가 중요하지 않은 회전과 동일한 경우에만 문자열이 주기적이라는 관찰에 기초합니다.@AlexiTorhamo의 첫 번째 할 수 위해 @를 표합니다. 그러면 우리는 첫 번째 발생의 색인에서 주요 기간을 회복할 수 있습니다.s(s+s)[1:-1]및 옵션 정보를 알려주시기 바랍니다.start ★★★★★★★★★★★★★★★★★」endPython 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개(단, 가능한 한 적은 수) 포함하는 일치 그룹입니다(비문자가 원인).\1+는 첫 번째 부분에서 일치하는 그룹의 적어도1개의 반복을 체크합니다.$는 문자열의 끝을 체크하여 반복된 서브스트링 뒤에 여분의 비문헌 콘텐츠가 없는지 확인합니다(또한 를 사용하면 반복된 서브스트링 앞에 비문헌 텍스트가 없는지 확인합니다).
3.에서는 Python 3.4를 할 수 .$(적어도 2.3 이전 Python에서는) 다른 방법으로 regex와 함께 사용합니다.^(.+?)\1+$이 모든 것은 다른 어떤 것보다도 개인적인 취향에 달려있다.
문자열을 반복으로 간주하려면 문자열의 길이를 반복 시퀀스의 길이로 나눌 수 있어야 합니다.이 는 that면면면, 면면기면 given given given given given given given given given given given given 에서 길이의 제수를 생성하는 이다.1로로 합니다.n / 2include는로 나누고 합니다.
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하면 Python 2를 할 수 .//@@타이거호크T3님 감사합니다.
//연산자는 Python 2와 Python 3 모두에서 정수 나눗셈을 수행하므로 두 버전을 모두 지원하도록 답변을 업데이트했습니다. 기판을 사용하여 입니다.all생성기 표현식입니다.
UPDATE: 원래 질문의 변경에 따라 코드가 갱신되어 최소 반복 서브스트링이 있는 경우 반환됩니다.None@@godlygeek은 @godlygek를 사용하라고 했습니다.divmod divisors또한 그에 맞게 코드가 업데이트되었습니다. 제제 it 、 it 、 div 、 div 、 div 、 div 、 div it 。n으로 ('오름차순')n그 자체입니다.
하이 퍼포먼스 추가 갱신: 여러 테스트 결과, 단순히 문자열의 동일성을 테스트하는 것이 Python의 슬라이싱 또는 반복기 솔루션 중 최고의 성능을 발휘한다는 결론을 얻었습니다.그래서 @TigerhawkT3를 본받아 솔루션을 업데이트했습니다.지금은 전보다 6배 이상 빨라졌습니다. 눈에 띄게 타이거호크의 해결책보다는 빠르지만 데이비드의 해결책보다는 느립니다.
다음은 이 질문에 대한 다양한 답변에 대한 벤치마크입니다.테스트하는 문자열에 따라 성능이 크게 달라지는 등 몇 가지 놀라운 결과가 있었습니다.
Python 3에서 Python 3으로 됨).///정수 나눗셈을 보장합니다).잘못된 것을 발견하거나 함수를 추가하거나 다른 테스트 문자열을 추가하고 싶을 경우 Python 채팅룸에서 ping @ZeroPiraeus로 이동합니다.
요약하면, (이 코멘트를 통해) 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
위의 솔루션은 원래 솔루션보다 몇 퍼센트 느린 경우는 거의 없지만, 대개는 훨씬 더 빠릅니다. 때로는 훨씬 더 빠릅니다.긴 문자열에 대한 데이비드주의보다 빠르지 않고 짧은 문자열에 대한 0의 정규식 솔루션이 우수합니다.그것은 약 1000-1500자의 문자열로 가장 빨리 나온다(기써브에 대한 다윗교의 테스트에 따르면 - 그의 답을 보라).어쨌든 테스트한 모든 경우에서 두 번째로 속도가 빠릅니다(또는 더 우수합니다).고마워, That Weirdo.
테스트:
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) functiondisplices. function.displices in in 。
는 느릴 수 느릴 수 . 즉, is (UPD: 및는는)의 약수 달라지는 다른 수 있습니다n, 더 빨리 에 그 중 가 될 수 aaa....aab서 " " 가 n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a
우선 프리픽스 함수를 계산해야 합니다.
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
에서는 문자열 또, 「」를 합니다.*후보 시퀀스에서 풀렝스 문자열을 작성하려면 다음 명령을 사용합니다.
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하지 않을 수 있습니다.ababdiscloss.discloss.case.
여기 정규식이 없는 간단한 해결책이 있습니다.
「 」의 s 인덱스에서 ~ 0 의 1 starting1 、 1 、 1 、 1 、 1 。len(s) 서브스트링, 이 서브스트링이 확인합니다.substr반복 패턴입니다.는 '접속'을 통해 실행할 수.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"
저는 이 문제에 대한 8개 이상의 해결책으로 시작했습니다.일부는 regex(match, findall, split), 일부는 문자열 슬라이싱 및 테스트, 일부는 문자열 메서드(find, count, split)를 기반으로 합니다.각각, 코드의 선명도, 코드 사이즈, 속도, 메모리 소비량의 메리트가 있었습니다.여기에 답변을 올리려고 했는데, 실행 속도가 중요한 것으로 평가되었기 때문에 더 많은 테스트와 개선을 통해 이 결과를 얻었습니다.
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]각 루프에 변수를 직접 작성하지 않도록 합니다.
일반적인 하드웨어에 의한 표준 테스트에서 이것이 어떻게 동작하는지 알고 싶습니다.대부분의 테스트에서 David Zhang의 뛰어난 알고리즘에는 크게 못 미치겠지만 그렇지 않으면 상당히 빠를 것입니다.
나는 이 문제가 매우 직관에 어긋난다는 것을 알았다.내가 생각하기에 빠른 해결책은 느렸다.느린 것처럼 보이는 솔루션은 빨랐습니다!곱셈 연산자와 문자열 비교에 의한 Python의 문자열 작성은 매우 최적화되어 있는 것 같습니다.
이 함수는 매우 빠르게 실행됩니다(테스트가 완료되었으며 10만 문자를 초과하는 문자열의 경우 가장 빠른 솔루션보다 3배 이상 빠릅니다. 반복 패턴이 길어질수록 차이가 커집니다).이 방법에서는 다음과 같은 답변을 얻기 위해 필요한 비교 횟수를 최소화하려고 합니다.
def repeats(string):
n = len(string)
tried = set([])
best = None
nums = [i for i in xrange(2, int(n**0.5) + 1) if n % i == 0]
nums = [n/i for i in nums if n/i!=i] + list(reversed(nums)) + [1]
for s in nums:
if all(t%s for t in tried):
print 'Trying repeating string of length:', s
if string[:s]*(n/s)==string:
best = s
else:
tried.add(s)
if best:
return string[:best]
예를 들어 길이8의 문자열에서는 사이즈4의 fragment만 체크하고 길이1 또는 2의 패턴은 길이4의 패턴을 반복하기 때문에 더 이상 테스트할 필요가 없습니다.
>>> repeats('12345678')
Trying repeating string of length: 4
None
# for this one we need only 2 checks
>>> repeats('1234567812345678')
Trying repeating string of length: 8
Trying repeating string of length: 4
'12345678'
Zhang의 , 만약 를 가지고 있다면, 이것은 하지 않을 이다: 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'
문자열이 다른 문자열에서 반복되는지 여부만 알고 싶다면, 이것이 가장 좋고 가장 짧은 스니펫입니다.
def rep(repeat,fullstring):
return len(fullstring.split(repeat)) > 2
#rep('test', 'test -others-') - no
#rep('hello', 'hello world') - yes
언급URL : https://stackoverflow.com/questions/29481088/how-can-i-tell-if-a-string-repeats-itself-in-python
'programing' 카테고리의 다른 글
| PHP MYSQL - 열 이름을 사용하지 않고 자동 증분 필드를 사용하여 에 삽입합니다. (0) | 2022.09.06 |
|---|---|
| 오류: gem 네이티브 확장을 빌드하지 못했습니다. mysql2를 설치하는 동안 오류가 발생했습니다. (0) | 2022.09.06 |
| 파일로 인쇄 배열입니다. (0) | 2022.09.05 |
| NaN 유형이 '번호'를 반환하는 이유는 무엇입니까? (0) | 2022.09.05 |
| 문자열의 마지막 문자를 얻으려면 어떻게 해야 하나요? (0) | 2022.09.05 |