반복되는 스트링을 알아내려면 어떻게 해야 할까요?


스트링이 계속 반복되고 있는지 아닌지 확인하는 함수를 만들려고 합니다.

예를 들어

[
    '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',
]

는 그렇지 않은 경우입니다.

엄청 긴 스트링이 들어올 수도 있고, 반복되는 스트링이 엄청 길 수도 있습니다. 제가 쓰고 있는 방법은 처음부터 1개, 2개, 3개, ... 이런 식으로 반복되는 스트링 길이를 점점 늘여가는 방식인데요 이렇게 하니까 너무 느려서 다른 방법이 있는지 알고 싶습니다.

전체 스트링이 반복되고 있는지 아닌지, 반복되고 있다면 반복되는 스트링 중 제일 짧은 스트링이 뭔지 알 수 있을까요?

  • 2016년 01월 19일에 작성됨

조회수 157


1 답변


좋아요
0
싫어요
채택취소하기

제가 생각하기에 제일 간단하면서 반복을 피하는 방법은 다음과 같습니다

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

반복되는 구조와 그렇지 않은 구조간의 패턴을 분석해서 코드를 만들었습니다. 패턴은 다음과 같습니다.


1. 스트링 S의 전체가 반복되는 구조를 가진다면,

S = ABAB와 같이 표현할 수 있습니다. (단, A,B또한 string)

임의의 문자 a, b에 대해 A = aA', B = B'b라고 하면 S+S = ABABABAB = aA'BABABAB'b입니다.

따라서 S가 반복되는 구조를 가진다면 (S+S)[1:-1]A'BABABAB'으로 find(A'BABABAB', S)에서 무조건 원본에서 두 번째 AB가 시작되는 점을 return합니다.



2. 스트링 S가 반복되는 구조를 가지지 않는다면

S = AB와 같이 표현할 수 있습니다.(단, A, B는 서로 반복되지 않는 string)

임의의 문자 a, b에 대해 A = aA', B = B'b라고 하면 S+S = ABAB = aA'BAB'b 입니다.

따라서 S가 반복되는 구조가 아니라면 (S+S)[1:-1]A'BAB'이고 find(A'BAB', S)는 무조건 None을 return 합니다.


로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close