문자열 · KMP String
KMP Logic
본문에서 패턴을 찾는 KMP의 흐름을 따라가요. 글자가 틀려도 본문 위치는 되돌리지 않고, LPS 표만큼만 패턴을 되돌려요.
패턴 ABCDABD
- 비교 중인 본문
- 일치
- 불일치
본문 패턴
A
B
C
A
B
C
D
A
B
A
B
C
D
A
B
C
D
A
B
D
E
A
B
C
D
A
B
D
STEP 1 / 25scrollYProgress 0.00
이 단계에서는
KMP 탐색을 시작해요. 스크롤을 내려 보세요.
- 본문 위치
- 0
- 패턴 위치
- 0
- 찾은 횟수
- 0
아래로 스크롤하면 다음 단계로, 위로 스크롤하면 이전 단계로 돌아가요.
본문은 되돌아가지 않아요
일치하면 두 위치가 함께 한 칸씩 나아가고, 불일치하면 패턴 위치만 LPS 값으로 되돌아가요. 그래서 본문을 한 번만 훑어요.
getKMPSteps(text, pattern)
-> { textIndex, patternIndex,
isMatch, lps, foundIndices }