이번에는 지난 글에서 구현하는 방법을 알아본 접미사 배열과 lcp 배열을 어떻게 활용하는지 알아볼 것이다.
문제를 풀어보기 전에는 suffix array와 lcp array가 도대체 어떤 의미를 가지나.. 싶기도 한데, 우리는 보통 접두사, 접미사보다도 부분 문자열에 관련된 문제를 많이 해결하게 된다. 이때, 우리가 주목해서 기억해야 하는 것은 부분 문자열은 결국 접미사의 접두사라는 것이다. 그러면 suffix array를 구했고, suffix array에서 lcp를 구한 것은 공통된 접미사의 접두사, 즉 공통된 부분 문자열에 관한 정보를 얻었음을 의미한다.
<BOJ 1605 반복 부분문자열> https://www.acmicpc.net/problem/1605
이 문제는 지난번 라빈 카프를 설명했을 때에도 다루었던 문제로, 부분 문자열 내에서 최대 길이를 갖는 공통된 문자열을 찾는 문제이다. lcp 배열 각각은 공통된 접미사의 접두사, 즉 공통된 부분 문자열의 길이를 담고 있으므로, lcp 배열의 최댓값이 최대 길이의 공통된 부분 문자열이 된다. 이는 조금만 생각해보아도 자명하다.
단, lcp 배열의 크기를 n-1로 설정했기 때문에 n = 1인 경우 lcp 배열이 비어 있게 된다. 따라서 이때는 그냥 0을 출력하도록 예외처리만 조심하면 된다. 코드는 아래와 같다. 라빈 카프보다 전체 길이는 더 길지만 suffix array와 lcp array를 구하고 나면 바로 값을 얻을 수 있다.
import sys
input = sys.stdin.readline
from bisect import bisect_left
def count_sort(arr, key, k):
# count sorting by key[idx], range: 0 - k
n = len(arr)
cnt = [0] * (k+1)
for val in arr:
cnt[key[val]] += 1
pfs = [0] * (k+1)
for i in range(k):
pfs[i+1] = pfs[i] + cnt[i]
out = [0] * n
for val in arr:
out[pfs[key[val]]] = val
pfs[key[val]] += 1
return out
def make_suffix(s):
n = len(s)
if n == 0: return []
sa = [*range(n)]
uniq = []
for ch in sorted(s):
if not uniq or ch != uniq[-1]:
uniq.append(ch)
rank = [bisect_left(uniq, ch) for ch in s]
k = 1
while k < n:
key1 = [r+1 for r in rank]
key2 = [rank[i+k]+1 if i+k < n else 0 for i in range(n)]
sa = count_sort(sa, key2, max(key2))
sa = count_sort(sa, key1, max(key1))
cnt = 0
new_rank = [0] * n
new_rank[sa[0]] = 0
for i in range(1, n):
a, b = sa[i], sa[i-1]
ra, rb = rank[a], rank[b]
rka = rank[a+k] if a+k < n else -1
rkb = rank[b+k] if b+k < n else -1
if ra != rb or rka != rkb:
cnt += 1
new_rank[a] = cnt
rank = new_rank[:]
if cnt == n-1: break
k *= 2
return sa
def makelcp(s, sa):
n = len(s)
if n <= 1: return []
rev = [0] * n
for i, p in enumerate(sa):
rev[p] = i
lcp = [0] * (n-1)
prvl = 0
for i in range(n):
r = rev[i]
if r == 0: prvl = 0; continue
j = sa[r-1]
while i+prvl < n and j+prvl < n and s[i+prvl] == s[j+prvl]:
prvl += 1
lcp[r-1] = prvl
if prvl: prvl -= 1
return lcp
n = int(input())
s = input().rstrip()
if n > 1: print(max(makelcp(s, make_suffix(s))))
else: print(0)
<BOJ 9249 최장 공통 부분 문자열> https://www.acmicpc.net/problem/9249
이번에는 앞서 풀어본 문제와 약간 다른데, 공통 부분 문자열을 같은 문자열 내에서 찾는 것이 아니라 다른 문자열 내에서 찾는 것이다. 이 경우에도 여전히 라빈 카프 알고리즘과 매개변수 탐색을 이용한 풀이가 가능하지만, 여기서는 접미사 배열과 lcp 배열을 활용해 보자.
이 문제 역시 같은 문자열 내에서 반복되는 문자열을 찾는 문제로 환원하고 싶으므로 두 문자열을 연결하고 싶은 욕망이 생긴다. 그런데 두 가지 문제점이 생긴다.
1. 두 문자열을 이어붙이면서 생기는 부분 문자열 (즉, 두 문자열에 걸쳐 있는 부분 문자열)을 어떻게 제거할까?
2. 같은 문자열에서 여러 번 반복되는 문자열을 어떻게 제거할까?
먼저, 1번 문제는 두 문자열을 이어붙일 때 두 문자열 모두에서 사용하지 않는 문자 (ex: '#')를 끼워넣음으로서 방지할 수 있다. 2번 문제는 그냥 suffix array 상에서 인접한 두 개를 반복해서 확인하되 같은 문자열에서 온 값이라면 배제하는 방식으로 풀 수 있다. 왜일까? 두 문자열 $A$, $B$가 있고 이의 최대 공통 부분 문자열이 $C$라고 하자. 그런데 $C$가 suffix array 상에서 인접하지 않는다고 가정하면 suffix array 상에서 $A$에서 유래한 $C$로 시작하는 접미사와 $B$에서 유래한 $C$로 시작하는 접미사 사이에 다른 문자열이 존재해야 한다. 그러면 이 문자열 역시 $C$라는 문자열을 접두사로 가지는 접미사여야 하고, 그러면 이는 1번 문제를 제거했으므로 여전히 $A$와 $B$ 중 하나에 속한 문자열이면서 $C$를 문자열로 가지는 접두사이다. 따라서 $C$가 최대 공통 부분 문자열이라는 조건에 모순이 되거나 결국 언젠가는 인접하면서 공통 부분 문자열이 $C$가 되는 경우가 존재한다.
따라서 이를 구현하면 아래와 같다.
import sys
from bisect import bisect_left
input = sys.stdin.readline
def count_sort(arr, key, k):
# count sorting by key[idx], range: 0 - k
n = len(arr)
cnt = [0] * (k+1)
for val in arr:
cnt[key[val]] += 1
pfs = [0] * (k+1)
for i in range(k):
pfs[i+1] = pfs[i] + cnt[i]
out = [0] * n
for val in arr:
out[pfs[key[val]]] = val
pfs[key[val]] += 1
return out
def make_suffix(s):
n = len(s)
if n == 0: return []
sa = [*range(n)]
uniq = []
for ch in sorted(s):
if not uniq or ch != uniq[-1]:
uniq.append(ch)
rank = [bisect_left(uniq, ch) for ch in s]
k = 1
while k < n:
key1 = [r+1 for r in rank]
key2 = [rank[i+k]+1 if i+k < n else 0 for i in range(n)]
sa = count_sort(sa, key2, max(key2))
sa = count_sort(sa, key1, max(key1))
cnt = 0
new_rank = [0] * n
new_rank[sa[0]] = 0
for i in range(1, n):
a, b = sa[i], sa[i-1]
ra, rb = rank[a], rank[b]
rka = rank[a+k] if a+k < n else -1
rkb = rank[b+k] if b+k < n else -1
if ra != rb or rka != rkb:
cnt += 1
new_rank[a] = cnt
rank = new_rank[:]
if cnt == n-1: break
k *= 2
return sa
def makelcp(s, sa):
n = len(s)
if n <= 1: return []
rev = [0] * n
for i, p in enumerate(sa):
rev[p] = i
lcp = [0] * (n-1)
prvl = 0
for i in range(n):
r = rev[i]
if r == 0: prvl = 0; continue
j = sa[r-1]
while i+prvl < n and j+prvl < n and s[i+prvl] == s[j+prvl]:
prvl += 1
lcp[r-1] = prvl
if prvl: prvl -= 1
return lcp
s1 = input().rstrip()
s2 = input().rstrip()
s = s1 + '#' + s2
sa = make_suffix(s)
lcp = makelcp(s, sa)
ans = ''
for i in range(1, len(sa)):
if (sa[i] - len(s1)) * (sa[i-1] - len(s1)) < 0:
if lcp[i-1] > len(ans):
ans = s[sa[i]:sa[i]+lcp[i-1]]
print(len(ans))
print(ans)
<BOJ 11479 서로 다른 부분 문자열의 개수 2> https://www.acmicpc.net/problem/11479
문제 제목 그대로 서로 다른 부분 문자열의 개수를 구하는 문제이다. 이 역시 공통된 부분 문자열에 대한 정보를 lcp 배열에서 얻을 수 있다는 점을 생각하면 쉽게 풀 수 있는데, lcp 배열의 한 값이 3이라는 것의 의미는 연속한 suffix 2개는 길이 3의 공통 접두사를 가지므로 부분 문자열이 3번 중복됨을 의미한다.
따라서 중복되는 문자열의 전체 개수는 lcp 배열의 전체 총합과 같게 되며, 이를 코드로 구현하면 아래와 같다.
from bisect import bisect_left
def count_sort(arr, key, k):
# count sorting by key[idx], range: 0 - k
n = len(arr)
cnt = [0] * (k+1)
for val in arr:
cnt[key[val]] += 1
pfs = [0] * (k+1)
for i in range(k):
pfs[i+1] = pfs[i] + cnt[i]
out = [0] * n
for val in arr:
out[pfs[key[val]]] = val
pfs[key[val]] += 1
return out
def make_suffix(s):
n = len(s)
if n == 0: return []
sa = [*range(n)]
uniq = []
for ch in sorted(s):
if not uniq or ch != uniq[-1]:
uniq.append(ch)
rank = [bisect_left(uniq, ch) for ch in s]
k = 1
while k < n:
key1 = [r+1 for r in rank]
key2 = [rank[i+k]+1 if i+k < n else 0 for i in range(n)]
sa = count_sort(sa, key2, max(key2))
sa = count_sort(sa, key1, max(key1))
cnt = 0
new_rank = [0] * n
new_rank[sa[0]] = 0
for i in range(1, n):
a, b = sa[i], sa[i-1]
ra, rb = rank[a], rank[b]
rka = rank[a+k] if a+k < n else -1
rkb = rank[b+k] if b+k < n else -1
if ra != rb or rka != rkb:
cnt += 1
new_rank[a] = cnt
rank = new_rank[:]
if cnt == n-1: break
k *= 2
return sa
def makelcp(s, sa):
n = len(s)
if n <= 1: return []
rev = [0] * n
for i, p in enumerate(sa):
rev[p] = i
lcp = [0] * (n-1)
prvl = 0
for i in range(n):
r = rev[i]
if r == 0: prvl = 0; continue
j = sa[r-1]
while i+prvl < n and j+prvl < n and s[i+prvl] == s[j+prvl]:
prvl += 1
lcp[r-1] = prvl
if prvl: prvl -= 1
return lcp
s = input().rstrip()
n = len(s)
print(n*(n+1)//2 - sum(makelcp(s, make_suffix(s))))
<BOJ 10413 반복되는 부분 문자열> https://www.acmicpc.net/problem/10413
이 문제는 반복되는 부분 문자열의 개수를 중복을 허락하지 않고 세는 문제이다.
예를 들어, 문자열 ABRACADABRA의 lcp 배열을 살펴보자.
lcp
A 10 X
ABRA 7 1 (A, ABRA)
ABRACADABRA 0 4 (ABRA, ABRACADABRA)
ACADABRA 3 1 (ABRACADABRA, ACADABRA)
ADABRA 5 1 (ACADABRA, ADABRA)
BRA 8 0 (ADABRA, BRA)
BRACADABRA 1 3 (BRA, BRACADABRA)
CADABRA 4 0 (BRACADABRA, CADABRA)
DABRA 6 0 (CADABRA, DABRA)
RA 9 0 (DABRA, RA)
RACADABRA 2 2 (RA, RACADABRA)
반복되는 부분 문자열은 lcp 배열의 값이 3인 경우 그 위치에서 3만큼 생긴다. 하지만, 여기서 반복되는 부분 문자열에서 중복을 고려해야 한다는 점이 큰 문제이다.
A에서 ABRA로 넘어갈 때 $lcp[0] = 1$이고, 여기서 중복되는 문자열은 A이다.
ABRA에서 ABRACADABRA로 넘어갈 때 $lcp[1] = 4$이고, 여기서 중복되는 문자열은 A, AB, ABR, ABRA 4개인데, A는 이미 센 문자열이므로 여기서 추가되는 문자열의 수는 $lcp[1] - lcp[0]$이다.
ABRACADABRA에서 ACADABRA로 넘어갈 때 $lcp[2] = 1$인데, 여기서 중복되는 문자열은 A이고 이미 세었으므로 추가되지 않는다.
이런 과정을 일반화하면, $lcp[i-1] < lcp[i]$인 경우 $lcp[i] - lcp[i-1]$개의 부분 문자열이 새롭게 반복되는 부분 문자열이고, $lcp[i-1] \ge lcp[i]$인 경우 $lcp[i]$에서 중복되는 부분 문자열은 $lcp[i-1]$에서 이미 중복된 부분 문자열이므로 더하지 않아도 된다.
따라서 아래와 같은 코드로 문제를 해결할 수 있다.
import sys
input = sys.stdin.readline
from bisect import bisect_left
def count_sort(arr, key, k):
# count sorting by key[idx], range: 0 - k
n = len(arr)
cnt = [0] * (k+1)
for val in arr:
cnt[key[val]] += 1
pfs = [0] * (k+1)
for i in range(k):
pfs[i+1] = pfs[i] + cnt[i]
out = [0] * n
for val in arr:
out[pfs[key[val]]] = val
pfs[key[val]] += 1
return out
def make_suffix(s):
n = len(s)
if n == 0: return []
sa = [*range(n)]
uniq = []
for ch in sorted(s):
if not uniq or ch != uniq[-1]:
uniq.append(ch)
rank = [bisect_left(uniq, ch) for ch in s]
k = 1
while k < n:
key1 = [r+1 for r in rank]
key2 = [rank[i+k]+1 if i+k < n else 0 for i in range(n)]
sa = count_sort(sa, key2, max(key2))
sa = count_sort(sa, key1, max(key1))
cnt = 0
new_rank = [0] * n
new_rank[sa[0]] = 0
for i in range(1, n):
a, b = sa[i], sa[i-1]
ra, rb = rank[a], rank[b]
rka = rank[a+k] if a+k < n else -1
rkb = rank[b+k] if b+k < n else -1
if ra != rb or rka != rkb:
cnt += 1
new_rank[a] = cnt
rank = new_rank[:]
if cnt == n-1: break
k *= 2
return sa
def makelcp(s, sa):
n = len(s)
if n <= 1: return []
rev = [0] * n
for i, p in enumerate(sa):
rev[p] = i
lcp = [0] * (n-1)
prvl = 0
for i in range(n):
r = rev[i]
if r == 0: prvl = 0; continue
j = sa[r-1]
while i+prvl < n and j+prvl < n and s[i+prvl] == s[j+prvl]:
prvl += 1
lcp[r-1] = prvl
if prvl: prvl -= 1
return lcp
t = int(input())
for _ in range(t):
s = input().rstrip()
sa = make_suffix(s)
lcp = makelcp(s, sa)
tmp = 0; ans = 0
for i in range(len(s)-1):
if lcp[i] > tmp:
ans += lcp[i] - tmp
tmp = lcp[i]
print(ans)
여기까지 다양한 접미사 배열과 lcp 배열 활용 문제를 알아보았다. 이제 아호 코라식을 다룰 차례인데, 다음 블로그에서는 아호 코라식을 다루기에 앞서 필요한 트라이 자료구조에 대해 다루려고 한다.
'PS' 카테고리의 다른 글
| 2026 Kaist Run Spring Contest 후기 (1) | 2026.05.05 |
|---|---|
| PS 문자열 알고리즘 - 8. 1D Trie 구현 (4) | 2025.08.13 |
| PS 문자열 알고리즘 - 6. 접미사 배열과 lcp 배열 (0) | 2025.08.12 |
| PS 문자열 알고리즘 - 5. 라빈 카프 알고리즘 (해싱) (2) | 2025.08.10 |
| PS 문자열 알고리즘 - 4. Manacher 알고리즘 (4) | 2025.08.09 |