1. 문제 설명

찾기

2. 문제 분석

KMP를 통해 부분 문자열을 찾았을 때 해당 원본 문자열 인덱스에서 타겟 문자열의 길이를 뺀 값을 통해 일치하는 패턴이 시작하는 위치를 기록할 수 있다.

3. 나의 풀이

import Foundation

let T = Array(readLine()!.map{String($0)})
let P = Array(readLine()!.map{String($0)})

func KMP(source:[String], target:[String]) -> [Int] {
    let sourceCnt = source.count
    let targetCnt = target.count
    var answers = [Int]()
    
    var LPS = Array(repeating: 0, count: targetCnt)
    LPS = LPScompute(target:target, LPS:LPS)
    
    var sourceIdx = 0
    var targetIdx = 0
    
    while (sourceIdx < sourceCnt) {
        if target[targetIdx] == source[sourceIdx] {
            sourceIdx += 1
            targetIdx += 1
        } else {
            if targetIdx == 0 {
                sourceIdx += 1
            } else {
                targetIdx = LPS[targetIdx - 1]
            }
        }
        if targetIdx == targetCnt {
            targetIdx = LPS[targetIdx - 1]
            answers.append(sourceIdx - targetCnt + 1)
        }
    }
    return answers
}

func LPScompute(target:[String], LPS:[Int]) -> [Int] {
    var length = 0
    var idx = 1
    var LPS = LPS
    while (idx < target.count) {
        if target[idx] == target[length] {
            length += 1
            LPS[idx] = length
            idx += 1
        } else {
            if length == 0 {
                LPS[idx] = 0
                idx += 1
            } else {
                length = LPS[length - 1]
            }
        }
    }
    return LPS
}

let answers = KMP(source: T, target: P)
print(answers.count)
for answer in answers {
    print(answer, separator: " ")
}