[백준] 부분 문자열 with python(KMP 알고리즘)

KMP 알고리즘 문자열 검색 알고리즘으로 보통 ABC라는 문자열이 ABCDEFG과 같은 문자열에 포함여부를 알기 위해서는 시간 복잡도가 O(NM) 정도로 상당한 복잡도를 보이는 데 반해 KMP 알고리즘을 사용하게 되면 불필요한 계산을 건너뛰기 떄문에 복잡도를 O(N+M) 정도로 줄일 수 있다 접두사와 접미사 이 KMP 알고리즘을 이해하기 위해서는 먼저 접두사와 접미사에 대한 개념을 짚고 넘어가야 한다 접두사는 말그대로 문자열의 앞에 붙은 패턴을 의미하고 접미사는 문자열의 끝에 붙어있는 패턴을 의미한다 이것을 예로 들어 설명하면, "ABCDABC"라는 패턴이 있다면 접두사로 ABC, 접미사로 ABC가 패턴이 동일하게 반복되는 것을 알 수 있다. KMP 알고리즘에서는 위와 같은 접두사와 접미사가 같은 패턴을..

2021.04.03