16916

[python] 백준 - 16916. 부분 문자열

🤔문제 해결 G4 | 문자열, KMP 딱 봐도 너무 쉽지만 G5니까…. 다른 방법으로 풀어야 한다고 생각했다. 들어는 봤어도 한 번도 써본 적 없는 KMP 알고리즘을 써야 문제를 해결할 수 있다. KMP를 쓰면 브루트포스로 문자열 탐색하는 것보다 아주 빠르다. O(M+N) 한 시간 넘게 찾아가면서 공부했지만 설명하기는 너무 어렵다. 이해가 잘 안 된다. 나중에 한 번 더 봐야겠다. 대충 말해보자면 비슷한 패턴을 기억해뒀다가 패턴을 만나면 점프... (무슨 말인지 모르겠다) 어째 됐든 이 알고리즘은 많이 쓰이진 않지만, 적당히 알아만 두면 좋을 거 같다. 💻소스 코드 def kmp_match(txt: str, pat: str) -> int: # 스킵테이블 만들기 def make_skip_table(skip..