어려움문자열KMP

부분 문자열 찾기 (KMP)

본문 text와 패턴 pattern이 주어져요. pattern이 text 안에 나타나는 모든 시작 위치(0-based)를 오름차순 배열로 반환해요. 겹치는 경우도 모두 세요.

한 글자씩 밀며 매번 처음부터 비교하면 O(n·m)이에요. KMP는 패턴 안의 반복 구조를 미리 계산한 실패 함수를 써서, 불일치가 나도 본문 포인터를 되돌리지 않아요. 덕분에 O(n + m)이에요.

실패 함수 fail[i]는 '패턴의 앞 i+1글자에서, 접두사이면서 접미사인 가장 긴 길이'예요. 불일치가 나면 이 값만큼 패턴 포인터를 뒤로 보내 비교를 이어가요.

예시

예시 1

입력: text = "abababa", pattern = "aba"
출력: [0, 2, 4]
설명: "aba"가 0, 2, 4에서 겹치며 나타나요.

예시 2

입력: text = "hello", pattern = "ll"
출력: [2]

예시 3

입력: text = "abc", pattern = "xyz"
출력: []

제한 사항

1 ≤ pattern.length ≤ text.length ≤ 200,000
두 문자열은 소문자 알파벳으로 이루어져요.

먼저 패턴의 실패 함수를 만들어요(j를 두고 pattern[i]와 pattern[j]를 비교하며 채워요). 그다음 본문을 훑되, 불일치가 나면 패턴 포인터 j를 fail[j-1]로 보내고, 일치가 패턴 끝까지 가면 시작 위치 i - j + 1을 담고 j를 다시 fail[j-1]로 보내요.

javascript
Copy code
function kmpSearch(text, pattern) {
  const m = pattern.length;
  const fail = new Array(m).fill(0);
  let j = 0;
  for (let i = 1; i < m; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) j = fail[j - 1];
    if (pattern[i] === pattern[j]) fail[i] = ++j;
  }
  const found = [];
  j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = fail[j - 1];
    if (text[i] === pattern[j]) {
      if (++j === m) {
        found.push(i - j + 1);
        j = fail[j - 1];
      }
    }
  }
  return found;
}

이전 문제트리의 지름

다음 문제가장 긴 팰린드롬 부분 문자열

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.