z function 활용법 2 - prefix이면서 suffix인 문자열을 찾는 방법-

1. border

 

어떤 문자열의 prefix이면서 동시에 suffix이기도 한 부분문자열을 border라고 부른다.

 

이 border와 관련된 문제를 해결하는데 z function이 매우 강력하다.

 

z function의 정의에 대해 생각해본다면..

 

z[i]는 s와 s[i,...,n-1]의 가장 긴 공통 접두사의 길이를 뜻한다

 

https://deepdata.tistory.com/1000

문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 z 알고리즘 배우기

 

여기서 하나 더 생각해본다면, z[i] 값을 안다면... 유일하게 접두사를 결정지을 수 있다.

 

그러니까 길이가 3인 접두사는 2개 존재하지 않는다.

 

ABACDA인 문자열에서 길이가 3인 접두사는 오직 ABA밖에 없다.

 

따라서 z[i] = m이라면 s[0,1,2,...,m-1]이 s와 s[i,...,n-1]의 가장 긴 공통 접두사인데..

 

여기서 s[i,i+1,i+2,...,i+m-1]이 s[0,1,2,...,m-1]과 같다는 뜻이 된다.

 

여기서 i번째 접미사 s[i,i+1,...,n-1]의 길이는 n-i인데, 이 길이와 가장 긴 공통 접두사의 길이 z[i]가 서로 같다면?

 

 

결국 i번째 접미사 s[i,i+1,...,n-1]과 s의 가장 긴 공통 접두사의 길이가 n-i라는 뜻은, 

 

s[i,i+1,...,n-1]이 s의 접두사가 된다는 뜻이다.

 

즉, z[i] = n-i이면 s[i,...,n-1]은 s의 prefix이면서 suffix가 된다

 

 

2. 문제

 

13576번: Prefix와 Suffix (acmicpc.net)

13576번: Prefix와 Suffix

 

3. 풀이

 

z function으로 s와 s[i,...,n-1]의 가장 긴 공통 접두사의 길이를 모두 찾는다

 

여기서 z[0] = n으로 정의하자.

 

해당 문자열 자체도 prefix이면서 suffix이기 때문에 z[0] = 0으로 해버리면 하나 빼먹게 된다.

 

def z_function(s):
   
    n = len(s)

    z = [0]*n
    
    z[0] = n

    left = 0
    right = 0

    for i in range(1,n):
      
        if i < right:
          
            z[i] = min(right-i, z[i-left])

        while i+z[i] < n and s[z[i]] == s[i+z[i]]:
          
            z[i] += 1
      
        if i+z[i] > right:
          
            left = i
            right = i+z[i]
  
    return z

s = input()

z = z_function(s)

 

이 때, z[i] = n-i이면 prefix이면서 suffix이므로, 이를 만족하는 모든 z[i]를 찾는다

 

여기서 나중을 위해 answer에는 길이가 짧은 것부터 길이가 긴 순서대로 들어가도록

 

z배열을 역으로 순회한다.

 

접미사 길이가 짧을수록, 가장 긴 공통 접두사는 짧을 가능성이 높기 때문

 

n = len(s)

answer = []

for i in range(n-1,-1,-1):

    if z[i] == n-i:

        answer.append((z[i]))

 

 

근데 이제 문제는... 이러한 prefix이면서 suffix인 부분문자열이 몇번이나 나오는가를 찾는게 문제

 

그런데, 핵심적인 관찰은 z[i]가 유일하게 접두사를 결정짓는다는 것이다.

 

즉, 길이가 m인 접두사는 주어진 문자열에서 오직 하나밖에 없다.

 

예를 들어 ABCDABD에서 길이가 2인 접두사는 AB밖에 없다. 

 

또한 길이가 긴 접두사는 길이가 짧은 접두사를 포함한다.

 

즉, 위에서 접두사 ABC는 접두사 A, AB를 포함하고 있다.

 

따라서 answer에 z[i] = n-i인 z[i]를 모두 담아두고, z배열을 오름차순 정렬한 다음,

 

처음부터 순회해서 z[i]와 answer[j]가 같게 되는 그러한 위치 i를 찾았다면,

 

길이가 answer[j]인 prefix이면서 suffix인 부분문자열을 n - i번 나타난다.

 

예를 들어 생각해보면

 

ABACABA의 z배열은.. [7,0,1,0,3,0,1]이다.

 

여기서 prefix이면서 suffix인 부분문자열을 찾기 위해 z[i] = n-i인 i를 찾는다.

 

그러면 z[0] = 7, z[4] = 3, z[6] = 1임을 알 수 있는데.. 이는 각각 ABACABA와 ABA와 A가 prefix이면서 suffix임을 뜻한다.

 

실제로도 각각 ABACABA, ABA, A가 prefix, suffix에 나타나고 있다.

 

 

이제 문제는 A, ABA, ABACABA가 각각 부분문자열로 몇번 나타나는지를 찾아야하는데..

 

Z배열이 [7,0,1,0,3,0,1]이라서 Z배열을 단순하게 보면 A가 실제로는 4번 나타나고 있는데 길이가 1이라서 2번밖에 안보여

 

하지만, "길이가 긴 접두사는 길이가 짧은 접두사를 포함한다"는 관찰에 의해

 

Z배열을 순회해서 길이가 1 이상인 경우가 몇번 나타나는가? 세보면  4번

 

길이가 3 이상인 경우는 2번, 길이가 7이상인 경우는 1번임을 알 수 있다.

 

근데 단순하게 찾으면 모든 answer에 대해 순회한 다음, 해당 값 이상인 z[i]를 count하면..

 

$O(N^{2})$정도라서 오래걸릴것 같다

 

for j in range(len(answer)):
    
    count = 0
    
    for i in range(n):
    
        if z[i] >= answer[j]:
            
            count += 1

    print(answer[j],count)

 

그래서 z배열을 오름차순 정렬해두면...

 

[7,0,1,0,3,0,1]은 [0,0,0,1,1,3,7]이 될텐데... 처음으로 1이 나오는 위치를 찾는다면..?

 

 

그러면 n - i를 바로 print하고 넘어가면 된다.

 

이러면 $O(NlogN + N)$정도에 모두 찾을 수 있다

 

#prefix이면서 suffix를 모두 찾는 알고리즘

def z_function(s):
   
    n = len(s)

    z = [0]*n
    
    z[0] = n #z[0] = n으로 정의, 자기 자신도 접두사이면서 접미사가 된다

    left = 0
    right = 0

    for i in range(1,n):
      
        if i < right:
          
            z[i] = min(right-i, z[i-left])

        while i+z[i] < n and s[z[i]] == s[i+z[i]]:
          
            z[i] += 1
      
        if i+z[i] > right:
          
            left = i
            right = i+z[i]
  
    return z

s = input()

z = z_function(s)

n = len(s)

answer = []

#z[i]는 접두사를 유일하게 결정짓는다.
#즉, 주어진 문자열에서 길이가 m인 접두사는 유일하다. (예) ABACABA에서 길이가 2인 접두사는 AB

#z[i]값 만큼 i번째 접미사 s[i,i+1,..,n-1]이 가져가기 때문에, 
#z[i]가 i번째 접미사 길이 n-i만큼 된다면? 
#따라서 prefix이면서 suffix일려면, z[i] = n-i인 모든 z[i]를 찾는다

#특히, n-1부터 0으로 역방향으로 순회해서, answer에 길이가 짧은 값부터 길이가 긴 값으로 들어가도록 한다
for i in range(n-1,-1,-1):

    if z[i] == n-i:

        answer.append((z[i]))

print(len(answer))

#z배열을 오름차순으로 정렬한다.
z.sort()

j = 0

#길이가 긴 접두사는 길이가 짧은 모든 접두사를 포함한다.
#예) ABACABA에서 길이가 3인 접두사 ABA는 길이가 1,2인 접두사 A, AB를 포함한다.

#정렬된 z배열을 순회하면서 처음으로 answer[j]인 위치 i를 찾았다면,
#answer[j]인 prefix이면서 suffix인 부분문자열은 n-i번 나타난다.
for i in range(n):
    
    if z[i] == answer[j]:

        print(answer[j],n-i)
        
        j += 1