[백준] 1701 - Cubeditor (G2)

https://www.acmicpc.net/problem/1701

1701번: Cubeditor

같은 부분 문자열이 2개 이상 나타나는 가장 긴 부분 문자열의 길이를 찾는 문제이다.

나는 골드 3의 티어로 난이도를 낮게 매겼다.

 

나는 신촌 연합 알고리즘 캠프에서 배운 라빈 카프 알고리즘에 이분탐색을 더하여 풀었다.

이분탐색을 사용한 이유는 다음과 같다.

 

부분문자열의 길이가 n일 때 문제 조건을 만족한다면

이 해당 부분문자열의 부분문자열도 문제의 조건을 만족하므로

길이가 n 미만인 모든 부분문자열의 길이에 대해 조건을 만족한다.

 

거꾸로 부분문자열이 길이가 n일 때 문제 조건을 만족하지 않는다면,

이 길이가 n인 부분문자열에 어떤 문자를 첨가하든 문제 조건을 만족시킬 수 없으므로

길이가 n 이상인 모든 부분문자열에 대해 조건을 만족시킬 수 없다.

따라서 이분탐색으로 문제를 풀 수 있다.

 

하지만 이분탐색을 쓰지 않더라도 문제는 풀 수 있다.

문자열의 길이가 너무 짧기 때문이다.

 

이분탐색을 사용한 경우 164ms, 그냥 순회하면서 찾은 경우 2920ms

시간 차이는 좀 많이 나긴 한다.

 

이분탐색을 할 때, 조건을 만족하는지 확인하는 것은 라빈카프 알고리즘에 해시맵을 이용했다.

 

def isPossible(length):
    global s
    x = 1
    MOD = 2**64
    v = 0
    d = dict()

    # 초기값
    for i in range(length-1, -1, -1):
        v += (x*(ord(s[i]) - ord('a') + 1))
        v %= MOD

        if i > 0:
            x *= 27
            x %= MOD

    d[v] = 0

    for i in range(len(s) - length):
        firstCharValue = x * (ord(s[i]) - ord('a') + 1)
        firstCharValue %= MOD

        v -= firstCharValue
        v *= 27
        v += (ord(s[i+length]) - ord('a') + 1)
        v %= MOD

        try:
            t = d[v]
            return True
        except:
            d[v] = 0

    return False


s = input()
l, r = 1, len(s)
while l < r:
    mid = (l + r) // 2

    if not isPossible(mid):
        r = mid
    else:
        l = mid + 1

if len(s) == 1:
    print(0)
else:
    print(r - 1)