C++에서 가장 긴 해피 접두사(Longest Happy Prefix) 찾기

문제 개요

문자열 s가 주어졌을 때, 가장 긴 해피 접두사(happy prefix)를 찾는 것이 이번 문제의 목표입니다. 여기서 해피 접두사란 문자열 자기 자신을 제외했을 때, 접두사이면서 동시에 접미사가 되는 비어 있지 않은 부분 문자열을 의미합니다. 만약 조건을 만족하는 해피 접두사가 존재하지 않는다면 빈 문자열("")을 반환하면 됩니다.

예를 들어 입력이 "madam"이라면 출력은 "m"입니다. "madam"에는 자기 자신을 제외한 네 개의 접두사("m", "ma", "mad", "mada")와 네 개의 접미사("m", "am", "dam", "adam")가 있습니다. 이 중 접두사이면서 접미사이기도 한 가장 긴 문자열은 "m"입니다.

해결 접근 방식: LPS 배열 활용

이 문제는 KMP(Knuth–Morris–Pratt) 문자열 매칭 알고리즘에서 사용되는 LPS(Longest Proper Prefix which is also Suffix) 배열을 활용하면 효율적으로 해결할 수 있습니다. LPS 배열의 마지막 값이 곧 가장 긴 해피 접두사의 길이가 됩니다.

알고리즘의 단계는 다음과 같습니다.

lps() 함수를 정의합니다. 이 함수는 문자열 s를 입력으로 받습니다.
n := s의 길이
크기가 n인 배열 ret을 선언합니다.
j := 0, i := 1로 초기화합니다.
i < n인 동안 다음을 반복합니다.
- s[i]와 s[j]가 같다면:
  - ret[i] := j + 1
  - i를 1 증가
  - j를 1 증가
- s[i]와 s[j]가 같지 않다면:
  - j > 0이면 j := ret[j - 1]
  - 그렇지 않으면 i를 1 증가
ret 배열을 반환합니다.

메인 함수(longestPrefix)에서는 다음 과정을 수행합니다.

n := s의 길이
n이 1이면 빈 문자열을 반환합니다.
v := lps(s)를 호출합니다.
x := v[n - 1], 즉 가장 긴 해피 접두사의 길이를 구합니다.
ret을 빈 문자열로 초기화한 뒤, i가 0부터 x 미만일 때까지 ret에 s[i]를 이어 붙입니다.
ret을 반환합니다.

이 알고리즘의 시간 복잡도는 O(n)으로, 문자열 길이에 선형적으로 비례하기 때문에 매우 효율적입니다.

C++ 구현 예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector <int> lps(string s){
        int n = s.size();
        vector<int> ret(n);
        int j = 0;
        int i = 1;
        while (i < n) {
            if (s[i] == s[j]) {
                ret[i] = j + 1;
                i++;
                j++;
            }
            else if (s[i] != s[j]) {
                if (j > 0)
                    j = ret[j - 1];
                else {
                    i++;
                }
            }
        }
        return ret;
    }
    string longestPrefix(string s) {
        int n = s.size();
        if (n == 1)
        return "";
        vector<int> v = lps(s);
        int x = v[n - 1];
        string ret = "";
        for (int i = 0; i < x; i++) {
            ret += s[i];
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.longestPrefix("madam"));
}

입력

"madam"