- 문제:
문자열을 입력받아 다음의 조건을 만족하는 LPS*를 찾아 그 길이를 리턴해야 합니다.
참고
- LPS: 주어진 문자열의 가장 긴 접두어이자 접미어(Longest Prefix which is also Suffix)
- non-overlapping: 접두어와 접미어는 서로 겹치는 부분이 없어야 합니다. 다시 말해, prefix와 suffix는 문자열의 동일한 인덱스에 위치한 문자를 요소로 가지면 안 됩니다.
입출력예시
let output = LPS('abbbcc');
console.log(output); // --> 0
output = LPS('aaaa');
console.log(output); // --> 2
// prefix: str.slice(0, 2)
// suffix: str.slice(2)
// non-overlapping 조건이 없는 경우 정답은 4 입니다.
output = LPS('aaaaa');
console.log(output); // --> 2
// prefix: str.slice(0, 2)
// suffix: str.slice(3)
// non-overlapping 조건이 없는 경우 정답은 5 입니다.접두어, 접미어를 이해하는 것부터 난관이었다. "특정한 문자"를 기준으로 앞 뒤에 위치한 단어 구성 요소를 접두어, 접미어라는 것이라고 이해했다. 같은 캐릭터로 구성된 접두어, 접미어의 가장 긴 길이를 찾는 것이 LPS 알고리즘의 목표이다.
참조: https://gusdnd852.tistory.com/172
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]) {
// LPS 검사를 시작한 위치부터 지금까지 계속 같은 경우
// 다음 문자도 같은지 확인하기 위해 인덱스를 이동한다.
leftIdx++;
rightIdx++;
} else {
// leftIdx가 0인 경우, 단순히 rightIdx를 1 증가 (suffix의 시작점을 뒤로 한 칸 이동)
// prefix, suffix가 계속 일치하다가 중간에서 일치하지 않는 경우에도,
// 현재 suffix의 시작점을 뒤로 한 칸 이동한다.
rightIdx = rightIdx - leftIdx + 1;
leftIdx = 0;
}
}
// LPS가 없는 경우
return leftIdx;
};문자열을 반으로 나누어 왼쪽, 오른쪽 인덱스끼리 비교하여 같은 부분 문자열의 최대 길이를 반환한다.
하지만, 효율적인 알고리즘(O(N))으로 풀기위한 아래 식은 아직 헤매는 중이다.🤔
const LPS = function (str) {
// lps[i]는 0부터 i까지의 부분 문자열, 즉 str.slice(0, i + 1)에서 lps의 길이를 저장한다.
const lps = Array(str.length);
// lps[0]은 길이가 1인 문자열의 lps의 길이이므로 항상 0이다. (자기 자신 포함 금지)
lps[0] = 0;
let leftIdx = 0;
let rightIdx = 1;
// lps[i]를 1부터, 즉 문자열의 길이가 2일때부터 차례대로 구한다.
while (rightIdx < str.length) {
if (str[leftIdx] === str[rightIdx] && rightIdx >= str.length / 2) {
// 가장 단순한 경우를 생각해보면, 쉽게 이해할 수 있다.
// 1) 길이가 2 경우
// 2) 길이가 3 이상인데 전부 같은 문자인 경우
// 0부터 leftIdx까지 매칭이 되었으므로 매칭된 길이는 leftIdx + 1이다.
leftIdx++;
lps[rightIdx] = leftIdx;
rightIdx++;
} else {
// 중간에 매칭이 되지 않은 경우, leftIdx를 조정한다.
// 현재 lps[0]부터 lps[rightIdx - 1]까지 계산이 완료된 상태이다.
// 처음부터 다시 prefix, suffix 매칭을 하는 것이 원칙이지만
// 앞서 계산한 결과인 lps 배열을 통해 처음으로 되돌아갈 필요는 없다.
// 예. aaabaaaa
// 현재 leftIdx는 2, rigthIdx는 3, lps는 [0, 1, 2]인 상태라고 가정해보자.
// leftIdx가 1일 때까지, 즉 현재 leftIdx 직전(leftIdx - 1)까지는 매칭이 되었다.
if (leftIdx !== 0) {
leftIdx = lps[leftIdx - 1];
// Also, note that we do
// not increment i here
} else {
// rightIdx가 1인 경우, 즉 첫 iteration일 경우
// lps[rightIdx]가 0인 것은 명백하다. (예. ab)
// leftIdx가 0이라는 것은 처음부터 prefix, suffix 매칭을 하는 경우이다.
//
// lps가 존재하지 않는 경우이다.
lps[rightIdx] = 0;
rightIdx++;
}
}
}
const res = lps[lps.length - 1];
return res > str.length / 2 ? Math.floor(str.length / 2) : res;
};
Log