[백준 16916] 부분 문자열 (Swift)

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

KMP 알고리즘 | 문자열

(Knuth-Morris-Prett 이 만들어서 KMP 알고리즘. 이런거 보면 나도 친구들이랑 알고리즘 만들고 싶다 Sujeong-Hyein-Nawon SHN 알고리즘~ 음.. 신한은행 약자 같음)

 

문자열 두개가 주어진다. S, P가 주어지는데, S에 P가 속하는지, 즉 P가 S의 부분 문자열인지 판단해서 맞으면 1, 아니면 0을 출력하는 문제

 

접근방법

contain 쓰면 되겠네~ 했는데 swift contains로 했더니 시간초과남 시간초과가 안났으면 브론즈 2가 맞을 것 같은데

시간초과 때문에 KMP를 써야한다면..과연 브론즈가 맞는지..?

KMP알고리즘 처음 들어보고 이번에 공부해서 풀었으요. 그치만 KMP알고리즘 안에서 사용되는 배열인 pi 배열 만드는 데에도 KMP 알고리즘을 쓰는 것은 사실 100% 이해되진 않음..

 

KMP 알고리즘은 문자열 P에 대해서 pi라는 배열을 만듭니다. pi 배열에서 pi[i]는 P의 i 인덱스의 문자까지의 문자열만 봤을 때 접미사와 접두사가 일치하는 최대 길이를 저장함. 즉, ABA라면, pi[2] 는 1이 된다. 앞의 A와 뒤의 A 한자리만 같기 때문에, 그 전까지는 0이될거고, 만약 ABCAB라면, p[4]는 2가 될것 ('AB') 

 

이 pi배열을 요긴하게 사용해서 부분 문자열 탐색 시간을 줄이는 것이 KMP 알고리즘의 핵심인데,

원래 완전 단순한 방식으로 비교한다면 문자열 맨 앞부터 비교해가면서 틀린 부분이 나타나면 한칸 뒤로 옮겨서 다시 보고, 이런걸 반복해야할텐데 그럼 시간복잡도가 S의 길이 * P의 길이가 될 것임.

그치만 KMP알고리즘을 사용하면 S길이 + P길이 안에 계산이 가능하다고 한다.

 

pi배열을 만들었다면, 이제 S와 P를 비교하는 과정을 시작한다.

맨 앞부터 S와 P를 비교하는 것은 똑같은데, 틀린 부분이 나타났을 때 P를 한칸 이동하는게 아니라, 현재 S를 가리키는 i는 그대로 있는 상태에서, P를 가리키는 j인덱스를 P에서 접미사와 일치하는 접두사 구간의 바로 다음칸을 가리키게 함, 즉, i = 6, j = 6일 때 두 문자열이 틀어졌다면, 5일때까지는 일치했다는 뜻이니까, 그 구간에서 수미상관되는 구간을 알고 있고(pi) 그 구간은 이미 같은걸 아니까 그 다음것부터 보겠다. 라는 개념이 적용된 것 같다. (하..나중에 이걸 보고 제발 이해할 수 있기를 그냥 코드를 봐.. https://bowbowbow.tistory.com/6 이분이 엄청 설명 자세하게 잘 해주심)

 

pi배열은 일일이 만들어도 길이가 짧기 때문에 시간복잡도가 괜찮을 거라고 하는데,,KMP로 pi구하는건 따라해보면 이해는 가는데, 논리적으로 이해하긴 어려워서 그냥 단순하게 만들어도 괜찮지 않을까 싶습니다..

 

오답노트

!!! Pi 배열 만들때 문자열 P의 문자들을 비교해야되는데, Pi 배열 원소들을 비교하고 있었음;;; 하

 

소스코드

import Foundation

func solution() -> Int {
    let S:[String] = Array(readLine()!.map{String($0)})
    let P:[String] = Array(readLine()!.map{String($0)})
    
    func getPi(_ P: [String]) -> [Int] {
        let m = P.count
        var j = 0
        var pi:[Int] = Array<Int>(repeating: 0, count: m)
        for i in 1..<m {
            while j > 0 && P[i] != P[j] {
                j = pi[j-1]
            }
            if P[i] == P[j] {
                j += 1
                pi[i] = j
            }
        }
        return pi
    }
    
    let pi = getPi(P)
    
    var j = 0
    for (i,_) in S.enumerated() {
        while j > 0 && S[i] != P[j] {
            j = pi[j-1] // 다르면 j를 수미상관되는 구간 다음 문자열을 가리키도록 이동 (i는 그대로)
        }
        // j가 0이 되거나, S[i],P[j]가 같으면 나옴
        if S[i] == P[j] {
            j += 1
            if j == P.count {
                return 1
            }
        }
    }
    return 0
}

print(solution())