[Algorithm] LPS와 정규식

LPS 알고리즘을 정규식으로 풀어내는 방법에 대해 학습한다. (실패)

LPS (Longest Prefix which is also Suffix)

LPS(Longest Prefix which is also Suffix)는 주어진 문자열의 가장 긴 접두어이자 접미어의 길이를 찾아 내는 알고리즘이다.
non-overlapping(접두어와 접미어가 겹치치 않아야 함) 규칙을 적용하여 알고리즘을 풀어보았다.

function LPS(str) {
  let resultStr = '';
  
  for (let i = 0; i <= str.length / 2; i += 1) {
    let prefix = str.slice(0, i);
    let suffix = str.slice(str.length - i);
    
    if (prefix === suffix) {
      resultStr = prefix;
    }
  };
  
  return resultStr.length;
};

오늘은 알고리즘 푸는 것과 동시에, 정규식을 써서 문제를 풀어내는 것에 학습을 해본다.
정규 표현식을 쓰면 두 줄만에 끝난다(..)

function LPS(str) {
  const result = str.match(/(\w*).*\1/);
  return result[1].length;
};

이제 이 주문 같은 코드를 한 번 쪼개서 알아보자!

1. String.match() 메서드 : 인자로 들어오는 정규식과 문자열을 일치시킨 값을 Array로 반환한다.
2. \w* : 반복된(*) word. 알파벳, 숫자, _ 중의 한 문자임을 의미
3. \1 : \n은 정규식 내부의 n번째 괄호에서 대응된 부분에 대한 역참조라고 한다.(n은 양의 정수)

그만.. 알아보자... 정규식 진입 장벽이 꽤 많이 높다. 😭
이게 어떻게(..) 동일한 접두어와 접미사를 찾아내는 것인지... 아직 이해가 잘 안된다.
사실 여기 막혀서 이 글이 며칠 째 발행되지 못하고 막혀있는데..........
정규식이 체화되는 그 날, 이 비밀에 대해서 밝혀보도록 하겠다.. I'll be back.. 🥲