LPS : Longest Prefix which is also Suffix

문제 :

• 문자열을 입력 받아 다음의 조건을 만족하는 LPS를 찾아 그 길이를 리턴한다.

 

조건:

• non-overlapping. 즉, 접두어와 접미어는 서로 겹치는 부분이 없어야 한다.

 

참고:

• prefix(접두어)는 문자열의 첫 인덱스부터 시작하는 모든 부분 문자열을 의미한다.
• suffix(접미어)는 문자열의 마지막 인덱스부터 시작하는 모든 부분 문자열을 의미한다.

 

---

pseudocode

 

1. prefix이자 suffix인 것 중 가장 긴 부분 문자열을 구하면서 서로 겹치지 않으려면 

      - prefix는 최대 문자열 길이의 1/2지점까지이며

      - suffix는 문자열 길이의 1/2 지점부터 끝까지가 되어야 한다. (str의 길이가 홀수인 경우 prefix가 더 길다.)

  abaab를 예로 들면 prefix === { a, ab, aba}, prefix === {b, ab} 가 된다.

 

2. if(str[leftIdx] === str[rightIdx]) { 동시에 인덱스를 증가시킨다.}

    : 같은 문자를 찾아서 다음 문자도 일치하는지 확인하기 위해 동시에 인덱스를 증가시킨다.

 

3. if(str[leftIdx] !== str[rightIdx]) && if(str[leftIdx] ===0) { rightIdx를 증가시킨다.}

   : 아직 일치하는 것이 없는 경우 rightIdx만 증가시켜서 그 suffix의 두 번째 혹은 세 번째 등 다른 문자는 일치하는지 알아본다.

 

4. if(str[leftIdx] !== str[rightIdx]) && if(str[leftIdx] !==0) { leftIdx를 감소시킨다.}

   : 일치하는 문자들이 있다가 불일치를 만난 경우, leftIdx를 감소시켜서 해당 rightInx와 일치하는지 알아본다.

    *이 부분은 aaabbcaaaaab를 예제로 마지막에 다시 정리해보려고 한다.

 

5. 1~4까지를 while문에 넣어서 rightIdx가 str의 길이보다 작을 때까지만 탐색하도록 한다.

 

6. while문을 나오면 leftIdx를 반환한다.

 

 

 

---

코드 구현

const lps = function(str) {
  if(str.length < 2) return 0;
  
  let leftIdx = 0;
  let rightIdx = Math.ceil(str.length/2);
  
  while(rightIdx < str.length){
    if(str[leftIdx] === str[rightIdx]){
      leftIdx++;
      rightIdx++;
    }else if(str[leftIdx] === 0){
      rightIdx++;
    }else{
      leftIdx--;
    }
  }
  return leftIdx;
}

 

 

예제 1 : lps('abaab')

str : abaab

idx : 01234

prefix는 str[2]까지가 될 것이고 suffix는 str[3]부터 끝까지가 된다.

 

1. str[0]과 str[3]는 a로 같다. leftIdx++, rightIdx++

2. str[1]과 str[4]은 b로 같다. leftIdx++, rightIdx++

3. str[2]와 str[5]를 비교하려는데 rightIdx가 str.length와 같아졌으므로 while문을 나온다.

4. leftIdx인 2를 반환한다.

 

 

 

예제 2 : lps('aaabbcaaaaab')

str :  aaabbc aaaa  a b

idx : 012345 67891011

 

1. str[0]과 str[6]은 a로 일치하므로 인덱스를 둘 다 증가시킨다.

2. str[1]과 str[7]은 a로 일치하므로 인덱스를 둘 다 증가시킨다.

3. str[2]와 str[8]은 a로 일치하므로 인덱스를 둘 다 증가시킨다.

4. str[3]과 str[9]는 각각 b와 a로 일치하지 않으므로 leftIdx--한다.

5. str[2]와 str[9]는 a로 일치하므로 인덱스를 둘 다 증가시킨다.

6. str[3]와 str[10]은 각각 b와 a로 일치하지 않으므로 leftIdx--한다.

7. str[2]와 str[10]은 a로 일치하므로 인덱스를 둘 다 증가시킨다.

8. str[3]과 str[11]에서 rightIdx가 str.length보다 작지 않으므로 while문을 나간다.

9. leftIdx를 리턴하면 3이 반환된다.

 

불일치가 발생했더라도 prefix든 suffix든 위치만 조정하면 서로 같아질 수 있으므로

prefix의 위치를 조정해서 str의 길이까지 모두 탐색해보는 것이다.

 

리턴하는 leftIdx의 값은 일치하는 부분 문자열의 길이가 되기 때문에

leftIdx--의 의미는 결국 일치하지 않는 부분이 발생했을 때 그 길이를 차감하는 역할을 하게 된다고 이해하면 쉬울 것 같다.