글 읽기 - 어느 부분에서 틀린지 모르겠습니다 ㅠㅠ

sunpl13 1년 전 0

KMP 알고리즘으로 풀고 있었는데 13%쯤 틀렸다고 나와서 반례를 찾긴 했습니다.

abb abb abb abbc

b a

이거 반례인데 KMP에서 값을 못찾는데 어디서 틀렸는지 알려주실 고수님들 계신가요ㅠㅠㅠ

  function makeTable(pattern) {
    let patternSize = pattern.length;
    let table = Array.from({ legnth: patternSize }, () => 0);
    let j = 0;
    for (let i = 1; i < patternSize; i++) {
      while (j > 0 && pattern[i] !== pattern[j]) {
        j = table[j - 1];
      }
      if (pattern[i] === pattern[j]) {
        table[i] = ++j;
      }
    }
    return table;
  }

  function KMP(parent, pattern) {
    let table = makeTable(pattern);
    let parentSize = parent.length;
    let patternSize = pattern.length;
    let arr = [];
    let j = 0;
    for (let i = 0; i < parentSize; i++) {
      //i가 0부터 돌면 0번 인덱스부터 검사
      while (j > 0 && parent[i] !== pattern[j]) {
        j = table[j - 1];
      }
      if (parent[i] === pattern[j]) {
        console.log(parent[i], i, j);
        if (j === patternSize - 1) {
          console.log(i - patternSize + 1);
          arr.push(i - patternSize + 1);
          j = table[j];
        } else {
          j++;
        }
      }
    }
    return arr;
  }

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어느 부분에서 틀린지 모르겠습니다 ㅠㅠ

sunpl13 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말