5254. [파이썬 SW 문제해결 최적화] 1일차 - 부분 문자열

시발 뭐 이딴게 다있냐

이 문제와는 별개로 몇 군데를 찾아보니 접미어배열 자체가 유용한 듯 하다.

강의와 외부 코드를 참고해서 작성했다.

일단 set을 이용해서 꼼수 비슷하게 정답 하나 만들어놓고, 접미어 배열와 LCP배열 만들어 놓은거를 이용해서 푼 것과 비교해서 작성했다.

for i 문을 통해 A[i][1] 의 string을 보는데 A[i][1] 의 string도 앞에서부터 끊어 읽으면 set에서의 부분문자열을 읽는 것과 비슷해진다.

단지 이렇게 끊어 읽기만 하면 i의 뒤를 읽을 때 중복해서 읽는 문제가 생긴다.

가령 abac를 보면 처음엔 A[0][1]을 봐서 'abac'를 'a', 'ab', 'aba', 'abac'로 다 읽었다 치자.

그 뒤엔 A[1][1]을 보고 'ac'를 'a', 'ac'로 읽지만 이미 'a'는 중복이므로 이를 빼고 읽어야 한다.

하지만 이미 LCP를 통해 앞의 문자와 얼마나 중복되는 가를 이미 파악했다. 그래서 중복되는 만큼 더 건너뛰어서 시작하기 위해 LCP의 값을 이용한다.

import sys

# http://cd4761.blogspot.com/2017/02/trie-1.html
# http://cd4761.blogspot.com/2017/03/trie-2.html
# https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/
# http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221028710658
# https://swexpertacademy.com/main/talk/solvingTalk/boardCommuView.do?searchCondition=COMMU_DETAIL-COMMU_TITLE-NICK_NAME_TAG&commuId=AXAuybMapTADFAXq&searchKeyword=5254&orderBy=DATE_DESC&pageSize=10&pageIndex=1&&&&&&


def LongestCommonPrefix(a,b):
    i=0
    while i < min(len(a),len(b)):
        if a[i] != b[i]: break
        i += 1
    return i

sys.stdin = open("sample_input2.txt", "r")

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    # 그냥 배열로 하니까 안됨.
    # 진짜 접미어 트리 배열 써야 하는 듯..

    inp = input().split()
    n = int(inp[0])
    s = inp[1]

    print(s)
    print("n :",n)
    # 그냥 배열로 하니까 안됨.
    # 진짜 접미어 트리 배열 써야 하는 듯..
    sps = set()
    for i in range(len(s)):
        for j in range(len(s),i,-1):
            sps.add(s[i:j])
    sp = sorted(list(sps))
    print(sp)

    A = [[0] * 2 for _ in range(len(s))]
    for i in range(len(s)):
        A[i][0] = i
        A[i][1] = s[i:]
    # print(A)
    A = sorted(A,key=lambda a:a[1])
    print(A)
    LCP = [0] * len(A)
    LCP[0] = 0
    for i in range(1,len(A)):
        LCP[i] = LongestCommonPrefix(A[i-1][1],A[i][1])
    print(LCP)

    resultc = ''
    resultl = 0
    for i in range(len(A)):
        suffix_index = A[i][0]
        curstr = A[i][1]
        if n > len(curstr):
            n += LCP[i] - len(curstr)
        else:
            resultc = curstr[0]
            resultl = len(curstr[:(n+LCP[i])])
            break

    print("#{}".format(test_case),resultc,resultl)

    # ///////////////////////////////////////////////////////////////////////////////////