하도 검색을 많이 했더니 문제번호도 외웠다.
문제의 입력조건:
두 문자열 길이의 합은 20만을 넘지 않는다.
두 문자열로 이차원 배열을 만들면 대략 100억개의 원소를 갖게된다.
첫번째 풀이: 선형탐색
a = input()
b = input()
ret_x, ret_l = 0, 1
s = min(a, b)
big = max(a, b)
for x in range(len(big)):
i, l = 0, ret_l
while i+l < len(s) and x+l < len(big):
if s[i] == big[x] and s[i+l] == big[x+l] and s[i:i+l] == big[x:x+l]:
l += 1
working = s[i:i+l]
else:
i += 1
if ret_l < l:
ret_l = l
ret_x = x
print(ret_l)
print(big[ret_x: ret_x+ret_l])입력 조건을 보지않고 순수한 마음으로 선형탐색을 했다.
그 결과 시간초과 오류가 나게 되었다.
두번째 풀이: 동적계획법
s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)
retval = [0, 0]
dp = [[0]*(l2+1) for _ in range(l1+1)]
for i in range(l1):
for j in range(l2):
if s1[i] == s2[j]:
dp[i+1][j+1] = dp[i][j] + 1
if dp[i+1][j+1] > retval[0]:
retval = [dp[i+1][j+1], i+1]
print(retval[0])
print(s1[retval[1]-retval[0]:retval[1]])
검사 결과를 저장해놓고 재활용 하는 개념을 활용하여 풀어보았다.
그러나 나는 너무 순진했고
나의 답안은 백억개의 요소를 버티지 못하고 메모리 초과가 나게 되었다.
마지막 풀이: SA와 LCP
words = [input(), input()]
word = "$".join(words)
word_len = len(word)
sa = [i for i in range(word_len)]
rank = [ord(i) for i in word]
tmp = [0] * word_len
def f(x): return rank[x] if x < word_len else -1
t = 1
while t <= word_len:
sa.sort(key=lambda x: (f(x), f(x + t)))
p = 0
tmp[sa[0]] = 0
for i in range(1, word_len):
if f(sa[i - 1]) != f(sa[i]) or f(sa[i - 1] + t) != f(sa[i] + t):
p += 1
tmp[sa[i]] = p
print(sa, rank, tmp)
rank = tmp[:]
t <<= 1
result = [0]*word_len
for i in range(word_len):
rank[sa[i]] = i
length = 0
for i in range(len(word.split()[0])):
if not rank[i]:
continue
j = sa[rank[i] - 1]
while i+length < word_len and j+length < word_len and word[i+length] == word[j+length]:
length += 1
result[rank[i]] = length
length = length-1 if length else length
m = (0, 0)
for i, j in enumerate(result):
if 0 <= sa[i-1] + j - 1 < len(words[0]) and len(words[0]) < sa[i] + j - 1 < len(word):
m = max(m, (j, i))
if 0 <= sa[i] + j - 1 < len(words[0]) and len(words[0]) < sa[i-1] + j - 1 < len(word):
m = max(m, (j, i))
length, start = m
print(length)
print(word[sa[start]:sa[start]+length])
인터넷에 파이썬으로 설명된 풀이가 없어 그냥 cpp 문법 조금 공부하고 cpp에 있는걸 그대로 파이썬으로 옮겨왔다. 그 과정도 쉽지 않아. 끊임없이 메모리초과와 씨름하다, 결국엔 파이썬으로 구현하는 방법까지 어디서 알아내서 결국 문제를 종결지었다.
sa를 구현하는데, manber myers algorithm을 사용했다. 정렬시에 모든 문자열을 비교할 필요 없이, 단 두번으로 비교가 끝난다는 아이디어가 핵심이다. 이런 아이디어는 도대체 어떤 발상으로 나오는건가.
lcp를 구현하는데 핵심은, 접미 배열을 사전순이 아닌 길이순으로 나열했을 때에, lcp[s[i]]의 값은 lcp[s[i-1]]의 값보다 작거나 같다는 아이디어이다. 이건 꽤나 직관적으로 이해할 수 있다.
마지막으로 내가 원하는 출력을 만들어 내기 위해서, lcp 배열을 활용하여, 최댓값과 해당하는 인덱스를 이용하여 문자열을 복원하는 단계만 구현하면, 해답을 알 수 있게 된다.
lcp에 값을 넣을 때에 주의해야할 점은, 참조하는 sa값 두 개가, 각각 다른 입력값으로부터 나왔다는것을 보장해야하는 것으로, 나는 words[0]의 값을 기준으로 i와 j를 비교하는 방식을 이용했다.
if 0 <= sa[i-1] + j - 1 < len(words[0]) and len(words[0]) < sa[i] + j - 1 < len(word):이 부분
느낀점
논리를 이해하더라도 구현은 또 다른 문제라는 사실을 느끼며, 효율적이고 아름다운 프로그래밍을 위해서는 고수들의 세련된 작문을 경험해야겠다는 생각을 하게된다.
이 문제는 풀었다 라고 말하기엔 부끄럽고, 배꼈다 라고 하는게 맞겠다. 고집과 게으름 그 중간 어디에서 나는 적절히 행동한 것이 맞는걸까, 정신적 게으름에 빠져 쉬운길로 간건 아닐까, 그런 생각이 나를 괴롭힌다.
