문자열 - Z 알고리즘

Z 알고리즘

문자열 T 내에 단어 W가 몇번 사용되는지 확인하는 선형 시간복잡도(O(|W|+|T|)) 알고리즘

Z 배열

문자열 T에서 인덱스 k까지의 하위 문자열이 k 이후의 하위 문자열에서 몇번 반복되는지를 계산한 배열

• 문자열: aabcaabxaaaz
• Z배열: [0, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0]

const createZArray = (text) => {
    const textArray = Array.from(text);
    const ZArray = ["X"];
    const length = textArray.length;

    for (let i = 1; i < length; i++) {
      let counter = 0;
      for (let j = 0; j < length - i; j++) {
        if (textArray[j % i] === textArray[i + j]) {
          counter += 1;
        } else {
          break;
        }
      }
      ZArray.push(counter);
    }

    return ZArray;
  };

단어 W와 문자열 T를 구분자 $로 조합한 뒤에 Z 배열을 생성하고, 패턴의 길이와 같은 값을 가지는 인덱스를 배열로 반환한다.

const ZAlogirthm = (text, pattern) => {
  const concatText = `${pattern}$${text}`;
  const patternLength = pattern.length;
  const ZArray = createZArray(concatText);

  const answer = [];

  ZArray.forEach((value, index) => {
    if (value === patternLength) {
      answer.push(index - (patternLength + 1));
    }
  });

  return answer;
};