만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 13713 문자열과 쿼리

23 Jun 2021

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

문자열 S = S1S2…SN이 주어질 때 F(i)는 S와 S1S2…Si의 가장 긴 공통 접미사의 길이로 정의된다. S와 i가 주어졌을 때 F(i)를 구하는 문제이다. 앞에서 배웠던 Z알고리즘을 활용하려고 보니 뭔가 이상하다. Z알고리즘은 Si~SN의 가장 긴 공통 접두사였는데 이번에는 형태가 조금 다르다.

하지만 해법은 간단하다. 문자열 S를 뒤집어서 SN~S1의 형태가 된다고 생각하자. Z[N-i]은 뒤집힌 S와 Si~S1의 가장 긴 공통 접두사의 길이 로 정의된다. 이는 우리가 구하고자 했던 S와 S1~Si의 공통 접미사 길이와 같다. 따라서 문자열을 뒤집어서 Z알고리즘을 적용시킨 후에 다시한번 뒤집어서 출력해주면 되는 문제이다.

파일의 입력이 크기때문에 fread를 해줘야 시간초과가 안난다. 관련 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였다. <출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>

/*
 fread 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였습니다.
 <출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>
*/

import Foundation

final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        return buffer[index]
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}

func Z(str: [Character]) -> [Int] {
    let n = str.count
    var l = -1, r = -1
    var F = Array(repeating: -1, count: n)
    F[0] = n-1
    for i in 1..<n {
        if i <= r {
            F[i] = min(F[i-l], r-i)
        }
        while i+F[i]+1 < n && str[i+F[i]+1] == str[F[i]+1] {
            F[i] += 1
        }
        if r < i+F[i] {
            r = i+F[i]
            l = i
        }
    }
    return F
}
    
let fIO = FileIO()
var line = fIO.readString().reversed().map{Character(String($0))}
var result = Z(str: line)
result.reverse()
let m = fIO.readInt()
var str = ""
for _ in 0..<m {
    let q = fIO.readInt()-1
    str += "\(result[q]+1)\n"
}
print(str)

Related posts