만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 1605 반복 부분문자열

23 Jun 2021

https://www.acmicpc.net/problem/1605

길이 L의 문자열이 주어지면 이 문자열의 부분문자열 중 적어도 한 번은 반복되는 부분문자열을 반복 부분문자열이라고 부르기로 했을 때 가장 긴 반복 부분문자열의 길이를 구하는 문제이다.

반복 부분문자열은 결국에는 suffix array상에서 가장 가까운 두 suffix 문자열이 갖는 접두사의 길이와 같다는 것을 알아야한다. A라는 반복 부분문자열이 존재하고 가장 길다고 했을 때, A라는 부분 문자열을 맨앞에 포함하는 두 suffix는 suffix array상에서 인접할 수밖에 없다.

예를들어 문자열 aabcaabcd가 존재한다고 했을 때.

두 suffix는 suffix array상에서 바로 옆에 위치한다.

문제가 어려워보였지만 결국에는 LCP를 구하는 문제로 바꿔볼 수 있다.
최종적으로는 LCP값 중에서 최댓값을 구하면 되는 문제이다.

func compare(g: [Int], a: Int, b: Int, t: Int) -> Bool {
    if g[a] == g[b] {
        return g[a+t] < g[b+t]
    }
    else {
        return g[a] < g[b]
    }
}

func suffix(str: [Character]) -> [Int] {
    let n = str.count
    var g = Array(repeating: -1, count: n+1)
    var ng = Array(repeating: -1, count: n+1)
    var sfx = Array(repeating: -1, count: n)
    var t = 1
    
    for i in 0..<n {
        g[i] = Int(str[i].asciiValue!-96)
        sfx[i] = i
    }
    while t < n {
        sfx.sort(by: {compare(g: g, a: $0, b: $1, t: t)})
        ng[sfx[0]] = 0
        for i in 1..<n {
            if compare(g: g, a: sfx[i-1], b: sfx[i], t: t) {
                ng[sfx[i]] = ng[sfx[i-1]] + 1
            }
            else {
                ng[sfx[i]] = ng[sfx[i-1]]
            }
        }
        g = ng
        t <<= 1
    }
    return sfx
}

func LCP(str: [Character], SA: [Int]) -> [Int] {
    let n = str.count
    var strArr = str
    strArr.append("#")
    var lcp = Array(repeating: 0, count: n)
    var rank = Array(repeating: 0, count: n)
    for i in 0..<n {
        rank[SA[i]] = i
    }
    
    var len = 0
    for i in 0..<n {
        let k = rank[i]
        if k > 0 {
            while strArr[SA[k-1]+len] == strArr[i+len] {
                len += 1
            }
            lcp[k] = len
            if len > 0 {
                len -= 1
            }
        }
    }
    return lcp
}

readLine()
let line = readLine()!.map{Character(String($0))}
let sa = suffix(str: line)
let lcp = LCP(str: line, SA: sa)
print(lcp.max()!)

Related posts