접두사-접미사 테이블
KMP 문자열 검색에서 패턴 문자열의 각 위치마다 그 위치까지의 부분 문자열에서 접두사와 접미사가 몇 글자까지 겹치는지를 미리 계산해 둔 표다. 패턴 매칭 중 글자가 어긋나면 처음부터 다시 비교하지 않고 이 표를 보고 몇 칸을 건너뛸지 바로 알 수 있어서, 텍스트를 다시 훑지 않고 선형 시간으로 검색할 수 있다. 실패 함수 또는 부분 일치 테이블이라고도 부른다.
자신만의 철학을 만들어가는 중입니다.
최상단으로 이동했습니다!