C++에서 접미사이기도 한 가장 긴 접두사를 찾는 방법

문자열 s가 주어졌을 때, 자기 자신을 제외하고 s의 접두사이면서 동시에 접미사가 되는 가장 긴 부분 문자열을 찾는 문제입니다. 만약 그러한 접두사가 존재하지 않는다면 빈 문자열을 반환하면 됩니다.

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

해결 접근 방식

이 문제는 KMP 알고리즘에서 사용되는 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을 반환합니다.

메인 함수에서는 다음 단계를 수행합니다.

• n := 문자열 s의 길이
• n이 1이면 빈 문자열을 반환합니다.
• v = lps(s) 배열을 구합니다.
• x := v[n - 1] (접두사이자 접미사인 최대 길이)
• ret := 빈 문자열
• i가 x보다 작은 동안 ret에 s[i]를 하나씩 추가합니다.
• ret을 반환합니다.

아래 예제 코드를 통해 더 잘 이해할 수 있습니다.

예제 코드

#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("helloworldhello"));
}

입력

"helloworldhello"

출력

hello