Algorithm problem-19

1. 문제

• 문자열을 입력받아 LPS의 길이를 리턴
• non-overlapping, 동일한 인덱스의 요소를 사용하면 안됨

2. 시도

• 겹치지 않아야 하므로, 절반으로 나눠서 생각해보기로 하였음
• 앞과 뒤로 나눈 요소를 직접 비교해서 겹치는 순간을 카운팅 해보았음
• 앞은 for문, 뒤는 겹칠 때에 slice를 해서 그 다음 것과 비교하기로 했음
• 생각처럼 작동하지 않아 실패하였음
• LPS 정규식이 존재한다regexr

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

3. 수도코드

const LPS = (str) => {
  let mid = parseInt(str.length / 2)
  if (str.length % 2 === 1) {mid += 1}
  let cnt = 0;
  let front = str.slice(0, mid)
  let rear = str.slice(mid)
  while (rear.length > 0) {
   for (let i = 0; i < front.length; i++) {
      if (front[i] === rear[0]) {
        cnt++
        rear = rear.slice(1)
      } else {
        rear = rear.slice(1)
      }
    }
  }
  return cnt;
};

4. 레퍼런스

const LPS = function (str) {
    let result = '';
    // pre는 0번부터 +1씩 증가
    // suf는 end부터 +1씩 증가
    // pre가 mid까지 증가하면 종료
    // 각 길이별로 비교, 같았던 값의 길이를 저장
    // 저장한 길이값을 리턴
    for (let i = 0; i <= str.length / 2; i++) {
      let prefix = str.slice(0, i);
      let suffix = str.slice(str.length - i);
      if (prefix === suffix) {
        result = prefix;
      }
    }
    return result.length;
  };