suffix array 깊이 이해하기 1 -반복되는 부분 문자열 찾기-

1. 반복되는 부분 문자열 찾기

 

전체 문자열에서 적어도 두번 이상 나타나는 부분문자열

 

보통 "가장 긴 반복 부분 문자열"을 찾는 것에 관심 있다

 

예를 들어 "abcefgabc"에서 "abc"가 두번 나타나면서, 가장 긴 반복 부분 문자열이다.

 

찾는 방법은 생각보다 간단한데,

 

https://en.wikipedia.org/wiki/Substring

Substring - Wikipedia

 

1) 먼저 lcp배열이 "이웃하는 접미사들의 가장 긴 공통 접두사의 길이"를 나타낸다

 

2) 또한 "모든 부분문자열은 모든 접미사들의 접두사"이다. 동일하게 "모든 부분문자열은 모든 접두사들의 접미사"이다.

 

증명은 모르겠지만... 조금 생각해보면 그런것 같다

 

banana의 부분문자열은?

 

b, a, n, a, n, a

 

ba, an, na, an, na

 

ban, ana, nan, ana

 

bana, anan, nana

 

banan, anana

 

banana

 

접두사와 접미사는 부분문자열의 특수한 경우이며..

 

접미사는 banana, anana, nana, ana, na, a

 

각 접미사의 접두사를 나타내보면?

 

banana >>> b, ba, ban, bana, banan, banana

 

anana >>> a, an, ana, anan, anana

 

nana >>> n, na, nan, nana

 

ana >>> a, an, ana

 

na >>> n, na

 

a >>> a

 

놀랍게도 모든 부분 문자열을 나타내고 있다.

 

접두사를 구해본다면? banana, banan, bana, ban, ba, b

 

각 접두사의 접미사를 구해본다면?

 

banana >>> banana, anana, nana, ana, na, a

 

banan >>> banan, anan, nan, an, n

 

bana >>> bana, ana, na, a

 

ban >>> ban, an, n

 

ba >>> ba, a

 

b >>> b

 

역시 놀랍게도 모든 부분문자열을 나타내고 있다.

 

모든 접미사들의 접두사가 모든 부분문자열을 나타낼 수 있으며, lcp는 이웃하는 접미사들의 가장 긴 공통 접두사의 길이를 나타낸다..

 

두 사실을 종합해본다면...?

 

lcp가 최대인 경우가 전체 문자열에서 두번 이상 나타나며 가장 긴 부분 문자열이 된다는 뜻이다

 

따라서, 문자열에 대한 suffix array와 lcp를 구하고 lcp의 최댓값이 되는 위치 i를 찾는다.

 

그 i에 대응하는 위치는 suffix array[i]이고 가장 긴 공통 접두사는... lcp[i]만큼 접두사를 가져오면 되니까...

 

s[suffix_array[i]:suffix_array[i]+lcp[i]]가 된다

 

이것이 전체 문자열에서 두번 이상 나타나며 가장 긴 부분문자열이며, 그 길이는 lcp[i]

 

 

2. 연습문제

 

16415번: Repeated Substrings (acmicpc.net)

16415번: Repeated Substrings

 

3. 풀이

 

suffix array와 lcp를 구현하고, lcp배열을 순회해서 가장 큰 lcp값과 해당 위치를 찾는다.

 

실제 부분문자열을 찾아야하므로, s[suffix_array[i]:suffix_array[i]+lcp[i]]를 출력

 

#repeated substring

def counting_sort(suffix_array,rank,d,n):
    
    m = max(n,256)

    counting = [0]*(m+1)

    counting[0] = d

    for i in range(d,n):
        
        counting[rank[i]] += 1
    
    for i in range(1,m+1):
        
        counting[i] += counting[i-1]
    
    second = [0]*n

    for i in range(n-1,-1,-1):
        
        if i+d >= n:
            
            ind = n
        
        else:
            
            ind = i+d

        counting[rank[ind]] -= 1

        second[counting[rank[ind]]] = i
    
    counting = [0]*(m+1)

    for i in range(n):
        
        counting[rank[i]] += 1
    
    for i in range(1,m+1):
        
        counting[i] += counting[i-1]
    
    for i in range(n-1,-1,-1):
        
        counting[rank[second[i]]] -= 1
        
        suffix_array[counting[rank[second[i]]]] = second[i]
    
    return suffix_array

def compare(rank,a,b,d):
    
    if rank[a] == rank[b] and rank[a+d] == rank[b+d]:
        
        return 0
    
    else:
        
        return 1

def get_suffix_array(suffix_array,rank):
    
    d = 1

    while d < 2*n:
        
        suffix_array = counting_sort(suffix_array,rank,d,n)

        new_rank = [0]*(n+1)

        new_rank[suffix_array[0]] = 1

        for i in range(1,n):
            
            new_rank[suffix_array[i]] = new_rank[suffix_array[i-1]] + compare(rank,suffix_array[i-1], suffix_array[i],d)
        
        if new_rank[suffix_array[n-1]] == n:
            
            break
        
        rank = new_rank
        d *= 2
    
    return suffix_array

def kasai(suffix_array,s):
    
    lcp = [0]*n

    reverse_suffix_array = [0]*n

    for i in range(n):
        
        reverse_suffix_array[suffix_array[i]] = i
    
    k = 0

    for i in range(n):
        
        if reverse_suffix_array[i] == 0:
            
            continue
        
        adj = suffix_array[reverse_suffix_array[i]-1]

        while i+k < n and adj+k < n and s[i+k] == s[adj+k]:
            
            k += 1
        
        lcp[reverse_suffix_array[i]] = k
        
        if k > 0:
            
            k -= 1
    
    return lcp

s = input()

n = len(s)

suffix_array = [i for i in range(n)]
rank = [ord(s[i]) - ord('a') + 1 for i in range(n)]
rank.append(0)

suffix_array = get_suffix_array(suffix_array,rank)
lcp = kasai(suffix_array,s)

#전체 문자열에서 두번 이상 나타나는 가장 긴 부분문자열은..?
#lcp값이 가장 큰 위치 i를 찾고, 해당 s[suffix_array[i]:]에서 lcp값만큼 접두사로 가져오면 된다.
max_lcp = 0
ind = 0

for i in range(n):
    
    if lcp[i] > max_lcp:
        
        max_lcp = lcp[i]
        ind = i

print(s[suffix_array[ind]:suffix_array[ind]+max_lcp])

 

 

4. 연습문제2

 

10413번: 반복되는 부분 문자열 (acmicpc.net)

10413번: 반복되는 부분 문자열

 

5. 풀이

 

이 문제는 조금 더 어려운게, 반복되는 부분 문자열을 찾지만, 유일한 부분 문자열을 모두 찾아 개수를 세어야한다

 

예를 들어 생각해보자.

 

"aabaab"에 대하여, 모든 접미사는 aabaab, abaab, baab, aab, ab, b

 

정렬하면 aab, aabaab, ab, abaab, b, baab

 

이렇게 접미사배열을 얻는데, 이들의 lcp를 구한다고 생각해보자.

 

suffix	lcp
aab	0
aabaab
ab

 

aab에 대응하는 lcp는 정의하지 않으니 0이라 하고.. aabaab의 lcp를 구하기 위해서는 aab와 비교해서..

 

가장 긴 공통 접두사의 길이를 찾는다

 

그거는 aab로 3

 

suffix	lcp
aab	0
aabaab	3
ab

 

 

그러면 이 과정에서 반복되는 부분 문자열이 aab, aa, a 3개 있다는 것을 알 수 있는데 

 

이제 ab에 대응하는 lcp값을 구할려면 aabaab와 비교해서 가장 긴 공통 접두사의 길이를 찾는데, 그건 a로 1이다.

 

suffix	lcp
aab	0
aabaab	3
ab	1

 

근데 여기서 반복되는 부분 문자열은 a로 1개이다. 

 

그러면 여기서 생각할 수 있는게, suffix_array[i]에 해당하는 lcp[i]를 구하기 위해..

 

suffix_array[i]와 suffix_array[i-1]의 가장 긴 공통 접두사의 길이 a를 찾고

 

suffix_array[i+1]에 해당하는 lcp[i+1]을 구하기 위해

 

suffix_array[i+1]과 suffix_array[i]의 가장 긴 공통 접두사의 길이 b를 찾는다.

 

여기서 a = 3, b = 1이었는데.. 관찰할 수 있는 사실은

 

a > b이면, suffix_array[i], suffix_array[i-1]에 나타나는 반복 부분 문자열들이 suffix_array[i+1], suffix_array[i]에 나타나는 반복 부분 문자열을 모두 포함한다

 

반대로 a < b이면, suffix_array[i+1], suffix_array[i]에 나타나는 반복 부분 문자열들이 suffix_array[i], suffix_array[i-1]에 나타나는 반복 부분 문자열을 모두 포함한다

 

그림 그려보면 쉽게 이해할 수 있다.

 

aabaab를 기준으로 이전에 가장 긴 공통 접두사가 aab

 

aabaab를 기준으로 이후에 가장 긴 공통 접두사가 a라면? aab에 a가 모두 포함되어 있음

 

aabaab를 기준으로 이후에 가장 긴 공통 접두사가 aaba라면? aab 부분을 제외하고, "a"라는 새로운 반복 부분 문자열이 생김

 

 

따라서 각 문자열마다 suffix_array와 lcp 배열을 찾고, lcp배열을 순회한다.

 

이제 인접한 lcp[i+1] - lcp[i] > 0이면 그 차이만큼 새로운 반복 부분 문자열들이 생기는 것이므로 그 차이만큼 더해주고,

 

lcp[i+1] - lcp[i] < 0이면, suffix_array[i],suffix_array[i-1]에 나타나는 모든 반복 부분문자열들이 

 

suffix_array[i],suffix_array[i+1]에 나타나는 반복 부분문자열을 포함하게 된다.

 

그래서 이전에 더한 개수에 포함된 상태이므로 더해주면 안된다.

 

#count of all unique repeated substring

from sys import stdin

def counting_sort(suffix_array,rank,d):
    
    m = max(n,256)

    counting = [0]*(m+1)

    counting[0] = d

    for i in range(d,n):
        
        counting[rank[i]] += 1
    
    for i in range(1,m+1):
        
        counting[i] += counting[i-1]
    
    second = [0]*n

    for i in range(n-1,-1,-1):
        
        if i+d >= n:
            
            ind = n
        
        else:
            
            ind = i+d

        counting[rank[ind]] -= 1
        second[counting[rank[ind]]] = i
    
    counting = [0]*(m+1)

    for i in range(n):
        
        counting[rank[i]] += 1
    
    for i in range(1,m+1):
        
        counting[i] += counting[i-1]
    
    for i in range(n-1,-1,-1):
        
        counting[rank[second[i]]] -= 1
        suffix_array[counting[rank[second[i]]]] = second[i]
    
    return suffix_array

def compare(rank,a,b,d):
    
    if rank[a] == rank[b] and rank[a+d] == rank[b+d]:
        
        return 0
    
    else:
        
        return 1

def get_suffix_array(suffix_array,rank):
    
    d = 1

    while d < 2*n:
        
        suffix_array = counting_sort(suffix_array,rank,d)

        new_rank = [0]*(n+1)

        new_rank[suffix_array[0]] = 1

        for i in range(1,n):
            
            new_rank[suffix_array[i]] = new_rank[suffix_array[i-1]] + compare(rank,suffix_array[i-1],suffix_array[i],d)

        if new_rank[suffix_array[n-1]] == n:
            
            break
        
        rank = new_rank
        d *= 2
    
    return suffix_array

def kasai(suffix_array,s):
    
    lcp = [0]*n
    reverse_suffix_array = [0]*n

    for i in range(n):
        
        reverse_suffix_array[suffix_array[i]] = i
    
    k = 0

    for i in range(n):
        
        if reverse_suffix_array[i] == 0:
            
            continue
        
        adj = suffix_array[reverse_suffix_array[i] - 1]

        while i+k < n and adj+k < n and s[i+k] == s[adj+k]:
            
            k += 1
        
        lcp[reverse_suffix_array[i]] = k

        if k > 0:
            
            k -= 1
    
    return lcp

T = int(stdin.readline())

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

    n = len(s)

    suffix_array = [i for i in range(n)]
    rank = [ord(s[i]) - ord('a') + 1 for i in range(n)]
    rank.append(0)

    suffix_array = get_suffix_array(suffix_array,rank)
    lcp = kasai(suffix_array,s)
    
    #lcp[i] = suffix_array[i]와 suffix_array[i-1]의 가장 긴 공통 접두사의 길이
    #lcp[i-1] = suffix_array[i-1], suffix_array[i-2]의 가장 긴 공통 접두사의 길이
    
    #lcp[i] - lcp[i-1] > 0이면, lcp[i] - lcp[i-1]만큼 suffix_array[i]부분에서 새로운 반복된 부분문자열이 생겨났고
    #lcp[i] - lcp[i-1] < 0이면, suffix_array[i-1] 부분에 suffix_array[i]에서 생긴 모든 반복 부분 문자열이 포함되어 있으니 더해주면 안된다
    
    answer = 0

    for i in range(1,n):
        
        if lcp[i] - lcp[i-1] > 0:
            
            answer += (lcp[i]-lcp[i-1])
    
    print(answer)