[BOJ, Swift] 1786 - 찾기 ( with KMP 알고리즘 )

1786번: 찾기

긴 문자열 속에서 특정 문자열을 찾아내는 알고리즘이다. Knuth Morris Pratt의 앞글자를 따왔으며, 1번부터 특정 문자열의 길이만큼 접근하는 일반적인 탐색법은 시간 복잡도가 O((n-m)n)이지만, KMP 알고리즘을 활용하면 O(n + m)의 복잡도로 시간을 단축시킬 수 있다.

1. 파이 테이블 생성

사실 KMP 알고리즘은 특정 문자열에 한 번, 그리고 이를 통해 만들어진 파이 테이블을 바탕으로 전체 문자열에 한 번 적용하여 총 두 번 쓰인다.

특정 문자열에서 일부 문자열이 반복한다면, 전체 문자열을 탐색하는 과정에서 중간마다 반복되는 문자열의 위치를 저장하고 다음번 탐색에서는 이 지점부터 진행한다.

// 파이 테이블 생성
var pattern = readLine()!.map { String($0) }
var table = Array(repeating: 0, count: pattern.count)

var i = 0

for j in 1 ..< pattern.count {
    
    while i > 0 && pattern[i] != pattern[j] {
        // 일치하지 않는 부분부터 다시 탐색
        i = table[i - 1]
    }
    
    // 일치한다면, 다음 문자도 일치하는지 확인
    if pattern[i] == pattern[j] {
        i += 1
        
        // 일치하는 길이만큼 저장
        table[j] = i
    }
}

2. 탐색

같은 방식으로 한번 더 진행해준다.

var all_str = readLine()!.map { String($0) }
var ans: [Int] = []

var i = 0
for j in 0 ..< all_str.count {

	// 중간에 문자가 서로 다르다면, 이전으로 돌아와 다시 진행
    while i > 0 && pattern[i] != all_str[j] {
        i = table[i - 1]
    }
    
    // 문자가 같으면 다음 걸 비교
    if pattern[i] == all_str[j] {
        i += 1
        
        // 특정 문자열의 길이만큼 같다면, 해당 문자열은 겹친다고 판단
        if i == pattern.count {
        	
            // 겹치는 문자열의 시작 위치를 배열에 저장
            ans.append(j - i + 2)
            
            // 이어서 진행
            i = table[i - 1]
        }
    }
}