C++로 두 문자열의 최장 공통 접두사를 만드는 최소 회전(시프트) 횟수 구하기

두 개의 문자열 A와 B가 있고, 두 문자열의 길이는 서로 같다고 가정해 보겠습니다. 한 번의 시프트(shift) 연산으로 문자열 B를 한 칸씩 회전할 수 있으며, 목표는 A와 B 사이의 공통 접두사(prefix) 길이를 최대화하기 위해 필요한 최소 시프트 횟수를 구하는 것입니다.

예를 들어 A = "programminglanguage", B = "computerprogramming"이라고 할 때, B를 왼쪽으로 8번 회전하면 "programmingcomputer"가 되어 A와의 공통 접두사가 "programming"(길이 11)으로 최대가 됩니다. 따라서 최소 시프트 횟수는 8이며, 이때의 공통 접두사는 "programming"입니다.

접근 방법

모든 시프트 경우마다 매번 접두사를 일일이 비교하는 것은 비효율적입니다. 대신 문자열 B를 자기 자신 뒤에 이어 붙여 B = B + B로 만들면, 가능한 모든 회전 결과가 이 확장된 문자열 안에 그대로 포함됩니다. 따라서 각 시프트를 별도로 확인할 필요 없이, B + B 안에서 A의 접두사 중 가장 긴 것이 나타나는 위치만 찾으면 됩니다. 이때 그 시작 위치가 곧 필요한 최소 시프트 횟수가 됩니다.

이 탐색은 KMP(Knuth–Morris–Pratt) 알고리즘을 활용하면 실패 함수(접두사 함수)를 이용해 불필요한 비교를 건너뛰면서 선형 시간에 처리할 수 있습니다.

C++ 구현 예제

#include<iostream>
using namespace std;
void KhuthMorrisPatt(int m, int n, string B, string A) {
    int pos = 0, len = 0;
    int p[m + 1];
    int k = 0;
    p[1] = 0;
    for (int i = 2; i <= n; i++) {
        while (k > 0 && A[k] != A[i - 1])
            k = p[k];
        if (A[k] == A[i - 1])
            ++k;
            p[i] = k;
        }
        for (int j = 0, i = 0; i < m; i++) {
            while (j > 0 && A[j] != B[i])
                j = p[j];
            if (A[j] == B[i])
                j++;
            if (j > len) {
                len = j;
                pos = i - j + 1;
            }
    }
    cout << "Shift = " << pos << endl;
    cout << "Prefix = " << A.substr(0, len);
}
int main() {
    string A = "programminglanguage";
    string B = "computerprogramming";
    int n = A.size();
    B = B + B;
    KhuthMorrisPatt(2 * n, n, B, A);
}

실행 결과

Shift = 8
Prefix = programming

시간 복잡도

KMP 알고리즘의 전처리 단계는 패턴 길이 n에 대해 O(n), 탐색 단계는 확장된 문자열 길이 2n에 대해 O(n)의 시간이 소요됩니다. 따라서 전체 시간 복잡도는 O(n)으로, 브루트포스 방식의 O(n²)보다 훨씬 효율적입니다. 공간 복잡도 역시 실패 함수 배열과 확장된 문자열 저장을 위해 O(n)입니다.