파이썬 백준 9249 최장 공통 부분 문자열

A = input()
B = input()
l = A + '1' + B
lenl = len(l)
rank = [ord(x) for x in l]
def order(i) : 
    if i >= lenl : 
        return 0
    return rank[i]
 
suffix = [i for i in range(lenl)]
pow2 = 1
newrank = [0 for i in range(lenl)]
while pow2 <= lenl : 
    suffix.sort(key=lambda x: (order(x), order(x + pow2)))
    i, group = 0, 1
    newrank[suffix[i]] = group
    for i in range(1, lenl) : 
        if order(suffix[i]) != order(suffix[i-1])  or order(suffix[i] + pow2) != order(suffix[i-1] + pow2) : 
            group = group + 1
        newrank[suffix[i]] = group
    rank = newrank[:]
    pow2 = pow2 * 2
 
for i in range(lenl) : 
    rank[suffix[i]] = i
LCP = [0 for i in range(lenl)]
lcp = 0
for now in range(lenl) : 
    if rank[now] == 0 : 
        continue
    before = suffix[rank[now] - 1]
    big = max(before, now)
    while big + lcp < lenl and l[before+lcp] == l[now+lcp] : 
        lcp = lcp + 1
    LCP[rank[now]] = lcp
    if lcp != 0 : 
        lcp = lcp - 1
 
maxlength = 0
maxindex = 0
center = suffix[0]
for i in range(2, lenl) : 
    if suffix[i] < center < suffix[i-1] or suffix[i-1] < center < suffix[i] : 
        if LCP[i] > maxlength : 
            maxlength = LCP[i]
            maxindex = suffix[i]
print(maxlength)
print(l[maxindex : maxindex + maxlength])

세줄요약

1. A+B의 접미사가 사전순으로 정렬된 suffix array를 구한다.

2. suffix array의 각 원소에 대해 이전 원소와 몇자리까지 겹치는지 기록한 LCP를 만든다.

3. suffix array의 두 인접원소가 서로 다른 문자열에서 온 원소일 때, ([i]는 A의 부분인데 [i-1]은 B일때, 혹은 그 반대) max값과 비교해서 갱신한다. 이를 모든 원소에 대해 체크한 뒤 max값을 출력한다.

 

IDEA

어떤 문자열에 대해 suffix array를 만들어서 LCK를 구해보자.

LCK의 각 원소는 문자열에서 반복적으로 등장하는 중복 부분문자열의 길이가 된다.

그렇다면 두 문자열 A, B가 주어졌을때 그것을 하나로 합쳐보자.

L = A + B라고 할때, A와 B의 중복 부분문자열들도 L의 LCK에 포함된다.

LCK를 구하기 위해 suffix array의 연속된 두 원소를 비교하는 과정에서, 둘 중 하나는 A의 부분이고 하나는 B의 부분인 경우도 모두 포함하기 때문이다.

따라서 A+B의 suffix array와 LCK를 구한 뒤, LCK에서 두 비교대상이 각각 A, B인 경우 중 최장인 것을 고르는 것으로 A와 B의 최장 중복 부분문자열을 구할 수 있다.

 

line 1 ~ 9

인풋받은 두 문자열을 합친다. 둘 사이에는 A, B에 들어가지 않는 문자를 넣어 구분한다.

부분문자열을 정렬하여 suffix array를 만들기 위한 우선도를 출력하는 함수 order를 정의한다.

그냥 문자열의 자릿수만큼 sort를 쓴다면 내장함수 ord를 써도 된다.

하지만 이 문제의 경우 문자열이 너무 길기 때문에 특정한 알고리즘을 써서 sort의 횟수를 줄여야 한다.

그때마다 order의 기준이 바뀌니 rank라는 리스트에 order의 기준을 넣고, order()에서는 그것대로 리턴할 것이다.

 

line 11

아직 사전순으로 정렬되지 않은 suffix array를 만든다. 이때 접미사 부분문자열을 직접 넣으면 메모리를 0.5n^2만큼 먹으니 부분문자열을 넣지 않고, 몇 번째 글자부터 시작하는 접미사인지를 int로 기록한 것을 넣는다.

 

line 12 ~ 23

n자리 문자열을 정렬하려면 n번의 sort가 필요하다. 하지만 접미사의 특징을 이용하면 단축이 가능하다.

맨버 마이어스 알고리즘은 이 접미사의 특징을 이용하여 매 sort마다 정렬 기준을 조금 손본다.

이렇게 매 sort마다 최적화된 정렬 기준을 이용하여 불필요한 sort를 줄일 수 있다.

자세한 원리는 따로 글로 적어두었다. (https://uneducatedjungler.tistory.com/111)

여기서는 구현의 메커니즘 위주로 적어본다.

 

최초의 정렬에서 ord()값을 이용하여 0, 1번째 자리를 정렬한다. (line 15)

정렬된 suffix의 각 원소를 group으로 구분시키는데,

suffix[i]가 이전 원소보다 order가 크거나,  suffix[i+pow2](=suffix[i]보다 길이가 pow2만큼 짧은 접미사)가 이전 원소보다 order가 크다면 group을 +1하여 이전 원소와 다른 그룹에 들어가게 한다. (line 19 ~ 20)

order()함수의 새로운 정렬 기준이 될 newrank 리스트에 각 원소의 group을 기록한다. (line 21)

rank를 newrank로 덮어씌우고, 다음 정렬은 pow2 *2번째 자리수에 할 것이므로 pow2를 *2한다. (line 22 ~ 23)

 

여기까지의 코드가 맨버 마이어스 알고리즘을 이용한 logn번의 정렬로 suffix array를 구하는 과정이다.

 

line 25 ~ 38

사전순으로 정렬된 suffix array를 이용해서 각 원소의 lck를 구한다.

이때 하나하나를 다 구한다면 여기서도 시간을 엄청 잡아먹을 것이다.

맨버 마이어스 알고리즘이 접미사의 특징을 이용했듯이 여기서도 이용한다.

suffix[i]의 lcp가 0이 아니라면, i보다 길이가 1 작은 원소의 lcp는 그것보다 1 작은 값일 것이다.

어차피 첫자리 하나 없는것 빼면 다 똑같기 때문이다.

따라서 suffix array의 LCP를 채워나가는데 왼쪽부터 채우는 것이 아니라 길이가 긴 순서대로 채운다면, 위의 특징을 이용하여 불필요한 재검사를 생략할 수 있다.

LCP를 길이순으로 채우기 위해 rank를 길이로 바꿔주고 (line 25 ~ 26)

for now in range(lenl)의 for문을 돌려 LCP를 구하되, now가 아닌 rank[now]의 순서대로 구한다.

즉, suffix의 now번째 index의 LCP를 구하는 것이 아니라, suffix 어딘가에 있는 길이가 lenl-now인 접미사의 LCP를 구한다.

그렇게 구한 길이 lenl-now의 접미사의 lcp가 0이 아니라면 다음 원소(길이가 lenl-now-1인 접미사)의 lcp는 계산하지 않아도 -1값이니 0이 될때까지 계산을 생략하며 채워준다.

 

line 40 ~ 49

위의 두 과정으로 suffix array와 LCP까지 구했다면, 이제 그 구한 값들 중 문제의 조건에 맞는 경우만 골라야 한다.

line 3에서 A와 B 사이에 알파벳 소문자보다 ord가 작은 '1'로 구분을 했으므로, suffix[0]에 해당하는 접미사는 1로 시작한다. (사전순으로 정렬하면 '1'이 맨 앞이므로)

이를 center라고 했을 때, suffix[i]와 [i-1]의 center와의 대소관계가 서로 다르다면(line 44), 하나는 1 왼쪽, 하나는 1 오른쪽부터 시작하는 것이다. 이는 하나는 A의 부분문자열, 하나는 B의 부분문자열로 시작한다는 의미이다.

그리고 이때의 LCP는 A와 B의 공통 부분 문자열의 길이가 될 것이다.

따라서, for문을 모든 원소에 대해 돌면서 위의 조건을 만족하는 경우 중 가장 큰 LCP값과 그때의 index를 기록한다.

그리고 기록한 max로부터 전체 문자열 l에서 최장 부분 문자열을 출력할 수 있다. (line 48 ~ 49)

 

 

문자열 진짜 어지럽네...