C++로 여러 문자열 집합에서 가장 긴 공통 부분 시퀀스 찾는 방법

이 글에서는 여러 개의 문자열(시퀀스) 집합이 주어졌을 때, 모든 시퀀스에 공통적으로 포함되는 가장 긴 부분 시퀀스를 찾는 C++ 프로그램을 소개합니다. 이 문제는 널리 알려진 '최장 공통 접두사(Longest Common Prefix)' 문제와 본질적으로 같으며, 첫 번째 문자열을 기준으로 삼아 나머지 문자열들과 순서대로 비교하면서 공통된 앞부분을 점차 좁혀 가는 방식으로 해결할 수 있습니다.

알고리즘

시작
문자열 배열을 입력받는다.
함수 matchedPrefixtill(): 두 문자열 s1과 s2 사이의 일치하는 접두사를 찾는다 :
    n1 = 문자열 s1의 길이를 저장한다.
    n2 = 문자열 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
종료
시작
함수 matchedPrefix(): 문자열 배열 전체에서 가장 긴 일치 접두사를 반환한다 :
    for int i = 1 to n - 1
        pre = matchedPrefixtill(pre, a[i])
    return pre.
종료

예제 코드

#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" 세 개의 문자열이 입력으로 주어집니다. 먼저 첫 번째 문자열 "Tutorialspoint"가 기준(pre)이 되고, 이를 "Tutor"와 비교하면 공통 접두사 "Tutor"가 도출됩니다. 다음으로 이 결과를 "Tutorials"와 다시 비교해도 여전히 "Tutor"가 유지되므로, 최종 결과는 "Tutor"가 됩니다.

비교 과정에서 한 번이라도 공통 접두사가 빈 문자열이 되면 이후 단계에서도 결과가 달라지지 않으므로, 그 경우 프로그램은 "No matched prefix"(일치하는 접두사 없음)를 출력합니다.

참고 사항 및 시간 복잡도

엄밀한 의미의 '최장 공통 부분 수열(LCS)'은 문자들이 반드시 연속적일 필요는 없지만, 이 프로그램은 연속된 형태의 공통 접두사를 찾는 방식이라는 점에 유의하세요. 시간 복잡도는 문자열의 개수 N과 각 문자열의 평균 길이 M에 비례하여 O(N × M)이며, 비교 단계마다 공통 접두사의 길이는 줄어들거나 유지되기 때문에 실제로는 더 빨리 종료되는 경우가 많습니다.