백준: 1701 Cubeditor

문제

1701번: Cubeditor

 

문제 풀이

 입력된 문자열의 두 번 이상 나오는 부분 문자열 중 가장 긴 길이를 찾는 문제이다. 이는 앞서 다룬 16916 부분 문자열, 1786 찾기에서 문자열 일치에 따라 정보를 생성하는 `make_table`을 활용하면 해결할 수 있는 문제이다.

 

코드

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


if __name__ == "__main__":
    s = input()
    result = 0

    for idx in range(len(s)):
        sub_str = s[idx:len(s)]
        result = max(result, make_table(sub_str))

    print(result)