Z

길이 $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]$ 을 얻을 수 있다.

 

---

공부한 곳

https://anz1217.tistory.com/66

https://codeforces.com/blog/entry/3107