[백준] 16916 부분 문자열

문제

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

 

입력

s: String = 문자열
pattern: String =  S의 부분 문자열인지 확인해야할 pattern

1 <= s.count < 1,000,000
1 <= pattern.count < 1,000,000

결과

ans: Int = 부분문자열이 맡다면 1 아니면 0

해석

문자열과 패턴이 최대 100만가까이 되는걸 보니 브루투스 포스 brute-force  방식으로는 해결이 불가능해보인다.

이 문제는 문자열에서 특정 패턴을 찾아내는 전형적인 kmp 문제 

 

1) lps 배열을 구한 후 

2) kmp 를 진행한다.

 

코드

import Foundation

func computeLPS(_ pattern: [Character]) -> [Int] {

    let n = pattern.count
    
    var lps: [Int] = [Int](repeating: 0, count: n)
    
    var len = 0
    var pos = 1
    
    while pos < n {
        
        if pattern[len] == pattern[pos] {
            lps[pos] = len + 1
            pos += 1
            len += 1
            
        } else {
            
            if len == 0 {
                lps[pos] = 0
                pos += 1
            
            } else {
                len = lps[len-1]
            }
            
        }
        
        
    }
    
    return lps
}


func kmpSearch(_ s: [Character], _ pattern: [Character]) -> [Int] {
    
    let n = s.count
    let m = pattern.count
    
    let lps = computeLPS(pattern)
    
    var matchedStartIndex: [Int] = []
    
    var i: Int = 0
    var j: Int = 0
    
    
    while i < n {
        
        if s[i] == pattern[j] {
            i += 1
            j += 1
        } else {
            if j == 0 {
                i += 1
            } else {
                j = lps[j-1]
            }
            
        }
        
        if j == m {
            matchedStartIndex.append(i-j)
            j = lps[j-1]
        }
        
    }
    
    return matchedStartIndex
}

let s = Array(readLine()!)
let pattern = Array(readLine()!)

print(kmpSearch(s, pattern).isEmpty ? 0 : 1)