C++로 여러 문자열의 가장 긴 공통 접두사 찾기

이 글에서는 여러 개의 문자열로 이루어진 집합에서 모든 문자열에 공통으로 나타나는 가장 긴 접두사(Longest Common Prefix)를 찾는 C++ 프로그램을 살펴보겠습니다. 이 기법은 파일 경로 비교, 자동완성 기능 구현 등 다양한 분야에서 활용될 수 있습니다.

알고리즘

핵심 아이디어는 간단합니다. 첫 번째 문자열을 기준 접두사로 설정한 뒤, 나머지 문자열들과 하나씩 비교하면서 공통 부분만 남기는 방식입니다.

Begin
Take the array of strings as input.
function matchedPrefixtill(): find the matched prefix between string s1 and s2 :
    n1 = store length of string s1.
    n2 = store length of string s2.
    for i = 0, j = 0 to i <= n1 – 1 && j <= n2 - 1
        if s1[i] != s2[j]
            break
        result.push_back(s1[i])
    return result
End
Begin
function matchedPrefix(): returns the longest matched prefix from the array of strings:
    pre = first string of the array
    for int i = 1 to n - 1
        pre = matchedPrefixtill(pre, a[i])
    return pre.
End

동작 과정 요약:

• matchedPrefixtill(): 두 문자열 s1과 s2를 앞에서부터 한 글자씩 비교하여, 서로 다른 문자가 나오기 전까지의 공통 부분을 결과 문자열에 저장하고 반환합니다.
• matchedPrefix(): 배열의 첫 번째 문자열을 초기 접두사로 삼고, 두 번째 문자열부터 마지막 문자열까지 순차적으로 위 함수를 호출해 공통 접두사를 반복적으로 축소해 나갑니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;

// 두 문자열 간의 일치하는 접두사를 찾는 함수
string matchedPrefixtill(string s1, string s2) {
    string res;
    int n1 = s1.length(); // 문자열 s1의 길이 저장
    int n2 = s2.length(); // 문자열 s2의 길이 저장
    for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) {
        if (s1[i] != s2[j]) // 다른 문자가 나오면 중단
            break;
        res.push_back(s1[i]);
    }
    return (res);
}

// 배열 전체에서 가장 긴 공통 접두사를 구하는 함수
string matchedPrefix (string a[], int n) {
    string pre = a[0]; // 첫 번째 문자열을 초기값으로 설정
    for (int i = 1; i <= n - 1; i++)
        pre = matchedPrefixtill(pre, a[i]);
    return (pre);
}

int main() {
    string a[] = {"Tutorialspoint", "Tutor", "Tutorials"}; // 입력 문자열 배열
    int n = sizeof(a) / sizeof(a[0]);
    string res = matchedPrefix(a, n);
    if (res.length())
        cout<<"Longest common subsequence is matched - "<<res.c_str();
    else
        cout<<"No matched prefix";
    return (0);
}

실행 결과

Longest common subsequence is matched - Tutor

코드 설명

위 예제에서 세 문자열 "Tutorialspoint", "Tutor", "Tutorials"는 앞부분의 "Tutor"까지만 공통으로 일치합니다. 따라서 프로그램은 Tutor를 결과로 출력합니다.

만약 배열 내 문자열들이 하나라도 공통된 시작 부분을 갖지 않는다면, matchedPrefix() 함수는 빈 문자열을 반환하고 프로그램은 "No matched prefix"를 출력하게 됩니다.

이 알고리즘의 시간 복잡도는 최악의 경우 O(S)입니다. 여기서 S는 모든 문자열 길이의 합으로, 각 문자열을 한 번씩만 훑으면 되기 때문에 매우 효율적입니다.