문자열 · KMP String

LPS Builder

패턴 안에서 반복되는 구조를 찾아 LPS(Longest Prefix Suffix) 표를 만들어요. 이 표가 KMP에서 틀렸을 때 얼마나 건너뛸지 알려 줘요.

PATTERN ABCABDAB
  • 접두사 len
  • 일치
  • 불일치
index
0
1
2
3
4
5
6
7
Prefix · P[len]
A
B
C
A
B
D
A
B
Suffix · P[i]
A
B
C
A
B
D
A
B
LPS 표 (실패 함수)
0
·
·
·
·
·
·
·
STEP 1 / 10scrollYProgress 0.00
이 단계에서는

LPS[0]은 항상 0이에요. i=1, len=0에서 시작해요. 스크롤을 내려 보세요.

i (Suffix)
1
len (Prefix)
0
채운 칸
1/8

LPS[i]가 뜻하는 것

패턴 앞 i+1글자 안에서, 접두사이면서 접미사이기도 한 가장 긴 문자열의 길이예요. KMP가 틀리면 이 값만큼 되돌아가 비교를 이어 가요.

getLPSSteps("ABCABDAB")
-> 단계마다 { prefixIdx, suffixIdx,
  lps, isMatch } 스냅샷