문제https://www.acmicpc.net/problem/16916 입력s: String = 문자열pattern: String = S의 부분 문자열인지 확인해야할 pattern1 결과ans: Int = 부분문자열이 맡다면 1 아니면 0해석문자열과 패턴이 최대 100만가까이 되는걸 보니 브루투스 포스 brute-force  방식으로는 해결이 불가능해보인다.이 문제는 문자열에서 특정 패턴을 찾아내는 전형적인 kmp 문제  1) lps 배열을 구한 후 2) kmp 를 진행한다. 코드import Foundationfunc computeLPS(_ pattern: [Character]) -> [Int] { let n = pattern.count var lps: [Int] = [Int](rep..

KMP 알고리즘 정의KMP(커누스 모리스 프랫 3명의 사람이 같이 만들어서 KMP)알고리즘이며 불필요한 비교 즉, 어차피 틀릴걸 아는 부분은 건너뛰어버리는 원리를 이용하는 대표적인 문자열 매칭 알고리즘이다. 문자열 매칭이란 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾아내는 것을 의미한다. 쉽게 말하면 우리가 브라우저에서 ctrl+f를 통해 찾고자하는 문자열을 검색하는 행위라고 생각하면 된다. 과정1. 패턴 내 접두사 , 접미사를 활용하자.kmp 알고리즘의 핵심은 패턴의 접두사와 접미사 개념을 적극 활용하여 '반복되는 연산을 얼만큼 건너뛸 수 있는 지'에 대해 집중한다는 것이다. 패턴 내에 존재하는 접두사와 접미사가 '일치' 한다면 접미사를 접두사로 다시 바라봄으로써 문자열 탐색을 이어서 진행할..