1. KMP 알고리즘은 무엇인가?
Q: KMP는 긴 문자열 안에 짧은 문자열이 있는지 찾는 알고리즘이야?
✅ A: 맞아. KMP는 본문 문자열 A 안에 패턴 문자열 B가 연속적으로 완전히 일치하는 부분이 있는지를 찾는 알고리즘이야. 단순히 A, B, C 각각 문자가 있는지를 보는 게 아니라, "ABC" 전체가 본문 어딘가에 순서대로 쭉 있는지를 보는 거지.
2. 비교하다가 틀리면 다시 처음부터?
Q: A랑 B 비교하다가 틀리면 왜 다시 처음부터 비교 안 해?
✅ A: 그게 바로 KMP의 핵심. KMP는 "이미 일치했던 부분 중에서 다시 쓸 수 있는 게 있는지"를 따져서 다시 처음부터 안 가고, 그만큼만 점프해. 이 점프를 가능하게 해주는 게 바로 LPS 배열이야.
3. LPS 배열이 뭔데?
Q: LPS 배열은 뭐야? 왜 자기 자신이랑 비교하는 거야?
✅ A: LPS는 "Longest Prefix which is also Suffix". 즉, 패턴 문자열 자기 자신 안에서, 접두사와 접미사가 같은 가장 긴 길이를 각 인덱스마다 기록한 배열이야. 이걸 비교 도중 틀렸을 때 어디서부터 다시 비교할지를 알려주는 jump 지점으로 활용하는 거야.
4. LPS는 언제 계산해?
Q: 그럼 LPS는 본문 A랑 비교하면서 계산해?
✅ A: 아니야. LPS는 본문 A와 전혀 상관없이, 패턴 B만을 가지고 먼저 계산해. 패턴의 구조를 분석해서 jump 전략을 세워두는 전처리 과정이지.
5. LPS 값이 다 0이면?
Q: B = "ABCDEF"처럼 반복이 없으면 LPS는 전부 0이겠네?
✅ A: 맞아. 접두사와 접미사가 일치하지 않으면 LPS는 전부 0이야. 이럴 땐 점프할 수 있는 정보가 없기 때문에, 비교가 틀리면 매번 처음부터 다시 해야 해. KMP의 이점이 줄어드는 구조야.
6. LPS와 점프(jump)의 관계
Q: LPS랑 jump는 무슨 관계야?
✅ A: 본문과 비교 중 틀리면 j = LPS[j-1]로 점프한다는 게 핵심이야. 이건 "지금까지 맞았던 것 중 일부는 다시 쓸 수 있으니까, 거기서부터 다시 비교하자"는 전략이야. 점프를 빠르게 할 수 있도록 도와주는 지도가 바로 LPS.
7. 반복이 많을수록 더 좋음?
Q: 반복되는 구간이 많으면 KMP는 더 효율적이야?
✅ A: 정확해. 반복 구조가 많으면 LPS 값도 커지고, 점프도 멀리 갈 수 있어서 비교 횟수가 훨씬 줄어들어. 그래서 패턴이 길고 반복이 많을수록 KMP의 성능은 더욱 좋아진다.
8. 점프가 항상 되는 건 아님
Q: 틀릴 때마다 무조건 점프하는 건 아니지?
✅ A: 맞아. LPS[j-1]이 0이면 점프할 수 있는 정보가 없어서, 결국 처음부터 다시 비교하게 돼. 점프는 접두사 = 접미사가 있는 부분에서만 발생해.
KMP 핵심 정리
- LPS는 패턴 B 자체를 분석해서 만든다.
- 본문과 비교할 때 틀리면, LPS 배열을 보고 점프할 위치를 결정한다.
- 반복이 많을수록 LPS가 풍부하게 만들어지고, 점프가 많아져 성능이 좋아진다.
- LPS가 0이면 KMP는 단순 비교와 큰 차이가 없어진다.
