길이 $n$의 문자열 $S[0:n]$에 대하여 $Array Z[0:n]$를 $O(n)$에 구한다.
| $i$ | $Z$ | a | n | a | n | a | b |
| 0 | 6 | a | n | a | n | a | b |
| 1 | 0 | n | a | n | a | b | |
| 2 | 3 | a | n | a | b | ||
| 3 | 0 | n | a | b | |||
| 4 | 1 | a | b | ||||
| 5 | 0 | b |
$Z[i]$는 $S[0:]$와 $S[i:]$의 최대 공통 접두사의 길이이다.
코드는 다음과 같이 작성하였다.
def getZ(s):
l,r=0,0
ret=[0]*len(s)
ret[0]=len(s)
for i in range(1,len(s)):
if i>r:
l=r=i
while r<len(s) and s[r]==s[r-l]:
r+=1
ret[i]=r-l
r-=1
else:
if ret[i-l]<=r-i:
ret[i]=ret[i-l]
else:
l=i
while r<len(s) and s[r]==s[r-l]:
r+=1
ret[i]=r-l
r-=1
return ret
구간 $[l:r]$를 $S[l:r]$와 $S[0:]$의 접두사가 일치하면서 $r$이 최대인 구간으로 정의한다.
그러면 $Z[i]$는 각 $i$에서의 구간의 길이 $r-l$ 와 같다.
$Z[0]$은 S의 길이와 같음이 자명하다. $l$과 $r$을 $0$으로 초기화 한다.
이제 $i=1$부터 $i=|s|-1$까지 다음과 같은 과정을 반복한다.
- $Case1:$ $i>r$일 때
아무 정보가 없는 곳에 도달하였다.
$l$과 $r$을 현 위치로 이동하고, $S[r]$과 $S[r-l]$이 달라질 때 (구간 $[l:r]$의 정의를 위배) 까지 r을 오른쪽으로 이동한다.
이렇게 구한 $l$과 $r$의 차로 $Z[i]$의 값을 구할 수 있다.
- $Case2:$ $i≤r$일 때
현재 가지고 있는 정보가 완전할 때와 그렇지 않을 때로 나눌 수 있다.
$Z[i-l]≤r - i$에서 가지고 있는 정보는 완전하다.
$S[l:r]$과 $S[0:r-l]$이 같으므로 $Z[i]$와 $Z[i-l]$은 같다.
$Z[i-l]>r - i$에서 가지고 있는 정보는 제한적이다. $S[i:]$와 $S[0:]$의 접두사가 $r-i$글자 이상 일치할 수 있다는 뜻이다.
$l$을 $i$로 이동하고 $Case 1$과 같이 $r$을 이동시키면 $Z[i]$의 값을 구할 수 있다.
처음 표에서 쓴 문자열 ananab으로 자세히 알아보자.
$Z[0]$
문자열의 길이와 같으므로 6이다.
$l$과 $r$을 0으로 초기화 한다.
$Z[1]$ $(i=1, l=0, r=0)$
$i$가 $r$보다 커 $Case 1$에 해당한다.
| $S$ | a | n | a | n | a | b |
| $S[i:]$ | n | a | n | a | b | |
| $l, r$ | l, r = 1 |
$l$과 $r$을 $1(=i)$ 로 초기화 한 다음, $S[r]$과 $S[r-l]$이 달라질 때 까지 $r$을 오른쪽으로 이동시킨다.
하지만 처음부터 $S[1]$과 $S[1-1]$이 각각 n과 a로 다르므로 $l=1$, $r=1$로 끝난다.
그 결과 $Z[1] = 0$이다.
이렇게 바로 끝날 때 r이 l 뒤로 가는데, 그 다음 호출에선 다시 Case 1로 돌아와 l=r=i를 실행하므로 문제 없는 것 같다.
$Z[2]$ $(i=2, l=1, r=0)$
$i$가 $r$보다 커 $Case 1$에 해당한다.
| $S$ | a | n | a | n | a | b |
| $S[i:]$ | a | n | a | b | ||
| $l, r$ | l = 2 | r = 5 |
$l$과 $r$을 $2(=i)$ 로 초기화 한 다음, $S[r]$과 $S[r-l]$이 달라질 때 까지 $r$을 오른쪽으로 이동시킨다.
$r=5$에서 $S[5]$와 $S[5-2]$이 각각 b와 n으로 다르므로 $l=2$, $r=5$로 끝난다.
그 결과 $Z[2] = 3$이다.
$Z[3]$ $(i=3, l=2, r=4)$
$i$가 $r$이하이고, $Z[3-2]≤4 - 3$이므로 $Case 2$중 첫 째 경우에 해당한다.
| $S$ | a | n | a | n | a | b |
| $S[i:]$ | n | a | b | |||
| $l, r$ |
$S[l:r]$과 $S[0:r-l]$이 일치함을 확신할 수 있고, 실제로 ana (anana)로 같다.
따라서 $Z[3]$과 $Z[1]$도 같다고 확신할 수 있다.
$Z[3] = Z[1] = 0$ 이다.
$Z[4]$ $(i=4, l=2, r=4)$
$i$가 $r$이하이고, $Z[4-2]≤4 - 4$가 성립하지 않아 $Case 2$중 둘 째 경우에 해당한다.
| $S$ | a | n | a | n | a | b |
| $S[i:]$ | a | b | ||||
| $l, r$ | l = 4 | r = 5 |
$l$을 $i(=4)$로 이동하고, $S[r]$과 $S[r-l]$이 달라질 때 까지 $r$을 오른쪽으로 이동시킨다.
$r=5$에서 $S[5]$, $S[5-4]$이 각각 b, n으로 달라지므로 $l=4$, $r=5$로 끝난다.
따라서 $Z[4] = 1$이다.
$i=5$ 에서도 $Case 1$에서의 논리로 값을 구할 수 있고, 최종적으로 $Z = [6, 0, 3, 0, 1, 0]$ 을 얻을 수 있다.
공부한 곳
'알고리즘 > 필기' 카테고리의 다른 글
| 라빈-카프와 부분문자열 쿼리 (0) | 2022.07.22 |
|---|---|
| 연속한 수의 XOR sum (0) | 2020.12.25 |
| 치킨 쿠폰 (0) | 2020.11.25 |
| 유니온 파인드 (0) | 2020.09.11 |
댓글