모각코 1회차 회고(2020.07.06)
목표
https://seungbok3240.tistory.com/101
모각코 1회차(2020.07.06)
목표 - suffix array를 활용하여 LCP 구하는 알고리즘을 공부하고 활용하여 문제를 푼다.
seungbok3240.tistory.com
회고
목표 문제(백준)
https://www.acmicpc.net/problem/9248
9248번: Suffix Array
Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다. Suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 이를 Suffix 순으로 정
www.acmicpc.net
결과
문제를 풀기 위해서 suffix array와 이를 활용한 lcp을 구하는 알고리즘들에 대해서 공부하였다.
Python 기준 suffix array를 구하기 위해서 모든 접미사들의 배열을 만들어 정렬하여도 suffix array의 결과는 잘 나온다. 하지만 시간복잡도가 O(N^2logN)이 걸리게 된다. 이는 시간초과에 걸리게 되는 이유 중 하나이다. 또한 모든 접미사들을 저장한 후 정렬하게 되므로 메모리 초과에 걸리게 된다. 이를 해결하기 위해 Manber-Myers 알고리즘을 활용하면 시간복잡도가 O(NlogN^2)으로 줄어들게 된다.
위의 아이디어를 활용하여 문제를 풀어보려고 하였으나 매번 메모리 초과와 시간 초과에 걸렸다. 구글 검색 후 suffix array 알고리즘을 구현한 코드를 활용하여 문제를 통과하였다. 이를 바탕으로 suffix array, lcp 알고리즘에 대해서 더 공부해야겠다.
메모리 초과와 시간 초과의 이유
- 정확히 아직 모름!
코드 참고자료
https://louisabraham.github.io/notebooks/suffix_arrays.html
Suffix arrays in Python
What happened? When d.items() is sorted, it contains the real substrings. When you don't need to go really deep (like with a random string), it's not a problem. Because you don't compute the orders that are not useful, you limit the number of comparisons a
louisabraham.github.io
https://gist.github.com/prasoon2211/cc3f3d5b43a0885c0e7a
Python suffix array
Python suffix array. GitHub Gist: instantly share code, notes, and snippets.
gist.github.com
코드
from itertools import zip_longest, islice
def to_int_keys_best(l):
"""
l: iterable of keys
returns: a list with integer keys
"""
seen = set()
ls = []
for e in l:
if not e in seen:
ls.append(e)
seen.add(e)
ls.sort()
index = {v: i for i, v in enumerate(ls)}
return [index[v] for v in l]
def suffix_array_best(s):
"""
suffix array of s
O(n * log(n)^2)
"""
n = len(s)
k = 1
line = to_int_keys_best(s)
while max(line) < n - 1:
line = to_int_keys_best(
[a * (n + 1) + b + 1
for (a, b) in
zip_longest(line, islice(line, k, None),
fillvalue=-1)])
k <<= 1
return line
def lcp_array(s, sa):
# http://codeforces.com/blog/entry/12796
n = len(s)
k = 0
lcp = [0] * n
rank = [0] * n
for i in range(n):
rank[sa[i]] = i
for i in range(n):
if rank[i] == n - 1:
k = 0
continue
j = sa[rank[i] + 1]
while i + k < n and j + k < n and s[i + k] == s[j + k]:
k += 1
lcp[rank[i]] = k;
if k:
k -= 1
return lcp
def inverse_array(l):
n = len(l)
ans = [0] * n
for i in range(n):
ans[l[i]] = i
return ans
if __name__ == '__main__':
L = input()
inverse_suffix_array = suffix_array_best(L)
# print(inverse_suffix_array)
suffix_array = inverse_array(inverse_suffix_array)
# print(suffix_array)
for item in suffix_array:
print(item + 1, end=' ')
LCP = lcp_array(L, suffix_array)
LCP.pop()
LCP.insert(0, 'x')
print()
for item in LCP:
print(item, end=' ')