z - function 활용법1 -패턴이 문자열에서 몇번이나 나왔는가? 찾는법-

1. 부분문자열 검색

 

z-function의 대표적인 활용으로 특정한 문자열 t에 패턴 p가 몇번이나 존재하는지 찾아낼 수 있다.

 

이를 위해 새로운 문자열 s = p + # + t라는 문자열을 만들자.

 

여기서 #은 p와 t를 구분하기 위한 문자로, p,t 어디에도 등장하지 않는 문자여야한다.

 

이제 s에 대한 z-function을 계산하자.

 

[0,len(t)-1]의 임의의 i에 대하여... z[i+len(p)+1]이 len(p)와 같다면, t의 i번째 위치에 p가 1번 등장한 것이다.

 

문자열 t 위에 있는 위치인 i+len(p)+1에 대하여.. z[i+len(p)+1]은 s와 일치하는 가장 큰 공통 접두사의 길이로,

 

이게 len(p)라는 것은 s의 접두사인 p의 길이와 일치하기 때문이다.

 

 

 

 

2. 연습문제

 

1786번: 찾기 (acmicpc.net)

1786번: 찾기

 

9120번: Oulipo (acmicpc.net)

9120번: Oulipo

 

 

3. 풀이

 

KMP로도 풀어보았지만.. 정확히 Z function으로도 풀 수 있다.

 

https://deepdata.tistory.com/961

KMP(Knuth–Morris–Pratt) 알고리즘 배우고 부분문자열 검색하는 방법 익히기

 

text 속에 pattern이 몇번이나 나오는지 알고 싶다면, s = pattern + # + text로 만들고, s에 대한 z 배열을 구한다

 

i가 0부터 len(text)-1까지 순회하면서 z[i+len(p)+1]이 len(p)와 같으면 text내의 해당 위치 i에서 pattern이 등장한 것이다

 

KMP랑 속도는 비슷한듯..?

 

#1786번

 

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

t = input()
p = input()

z = z_function(p + "#" + t)

loc = []

for i in range(len(t)):
    
    if z[i+len(p)+1] == len(p):
        
        loc.append(i+1)

print(len(loc))
print(' '.join(map(str,loc)))

 

#9120번

 

from sys import stdin

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(z[i-left], right-i)

        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

T = int(stdin.readline())

for _ in range(T):
    
    p = stdin.readline().rstrip()
    s = stdin.readline().rstrip()

    z = z_function(p+'#'+s)

    count = 0

    for i in range(len(s)):
        
        if z[i+len(p)+1] == len(p):
            
            count += 1
    
    print(count)