[백준 파이썬] 1701 Cubeditor

문제

 

문자열이 주어지고 반복되는 문자열이 2개이상 있는 부분 문자열중 가장 긴 길이를 출력하면 된다.

---

풀이

주어진 문자열을 하나하나 탐색하면 당연히 시간초과가 나게된다.

따라서 Failure 함수를 사용하여 문자열이 존재하는지 파악해야한다.

Failure함수의 아이디어는 다음과 같다.

문자열에 반복되는 부분은 다시 검사할 필요가 없다라는 것이다.

 

다음과 같이 s1과 s2를 비교할 때 s2는 abab이므로 앞에 ab는 한번 비교해놓으면 두번째는 비교할 필요가 없다. 이 때 abab를 몇칸 이동해야하는지에 대한 정보를 담은게 fail 배열이다.

 

abcabcacab에 대한 문자열에 대해 fail배열은 다음과 같이 나오게 된다.

이때 최대 숫자인 4가 겹치는 문자열의 최대 길이가 된다.

 

다음을 구현하는 코드는 아래와 같다.

table = [0] * len(pattern)
j = 0

먼저 fail배열을 저장해줄 table과 j값을 초기화시기킨다.

 

for i in range(1, len(pattern)):
    while j > 0 and pattern[i] != pattern[j]:
        j = table[j - 1]

    if pattern[i] == pattern[j]:
        j += 1
        table[i] = j

이 후 1번째 문자부터 비교해준다. (첫 번째 문자에 대한 비교는 생략하기 때문)

이 후 i값을 증가시키면서 문자열의 비교를 시작한다. 초기 j값은 0이므로 첫번째 문자와 일치하는 문자를 찾는다.

만약 찾았다면 j값을 증가시키고 i값또한 증가시켜 다음 문자가 일치하는지 확인한다.

 

이 때 일치한다면 그대로 진행하고 일치하지 않는다면 j 값을 table[j - 1]로 이동시킨다. 

이 때 table[j - 1]값 이전의 값은 이미 비교를 마친 값이므로 이 값으로 이동한다.

이렇게 반복문을 마치면 fail배열이 완성된다.

 

 

ans = max(failure(pat))
    
print(ans)

마지막으로 반환된 배열의 최대값을 출력하면 된다.

 

 

 

---

코드

import sys
input = sys.stdin.readline

def failure(pattern):
    table = [0] * len(pattern)
    j = 0
    
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = table[j - 1]
        
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
    return table

pat = input()

ans = 0

for i in range(len(pat)):
    ans = max(ans, max(failure(pat[i:])))
    
ans = max(failure(pat))
    
print(ans)