JS-L4-027 / 고급 알고리즘
KMP 문자열 탐색
고급문제
text 안에 pattern이 처음 등장하는 UTF-16 인덱스를 반환하세요. 없으면 -1, 빈 패턴은 0입니다. KMP 접두어 표를 구현해보세요.
solve(...args) 함수에서 값을 반환하세요. console 출력은 정답 판정에 사용하지 않습니다.
입출력 예시
예제 1
입력: ["ababaca","abaca"] 반환: 2
예제 2
입력: ["abc","z"] 반환: -1
힌트
불일치 시 이미 일치한 접두어를 재사용하세요.
해설·정답 보기
접두어 표를 만들어 텍스트 위치를 뒤로 돌리지 않습니다. 결과 정확성만 자동 판정하며 KMP 사용 여부는 해설과 비교합니다.
function solve(text,pattern) { if(!pattern.length)return 0; const pi=Array(pattern.length).fill(0); for(let i=1,j=0;i<pattern.length;i++){while(j&&pattern[i]!==pattern[j])j=pi[j-1];if(pattern[i]===pattern[j])j++;pi[i]=j;} for(let i=0,j=0;i<text.length;i++){while(j&&text[i]!==pattern[j])j=pi[j-1];if(text[i]===pattern[j])j++;if(j===pattern.length)return i-j+1;} return -1; }solution.js결과 비교
코드는 이 브라우저에 자동 저장돼요.
풀이 결과
코드를 작성하고 채점하기를 눌러보세요.
학습용으로 제공된 조건을 확인해요. 알고리즘 사용 방식·설계 의도는 해설과 함께 비교해보세요.