문제 분석

두 개의 문자열이 주어질 때, 한 문자열의 접두사(prefix)이고 동시에 다른 문자열의 접미사(suffix)인 가장 긴 부분 문자열의 길이를 구해야 합니다. 두 방향 모두 검사해야 합니다: 첫 번째 문자열의 접두사 & 두 번째 문자열의 접미사, 그리고 첫 번째 문자열의 접미사 & 두 번째 문자열의 접두사.

핵심 아이디어

길이 k에 대해 검사할 때:

• 문자열 A의 앞 k글자가 문자열 B의 뒤 k글자와 일치하는지 확인
• 문자열 B의 앞 k글자가 문자열 A의 뒤 k글자와 일치하는지 확인

가능한 모든 길이에 대해 검사하여 최대값을 찾습니다.

최적화된 풀이

문자열 복사를 최소화하고 직접 인덱스 비교로 효율성을 높인 버전입니다:

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

// 두 문자열의 특정 위치에서 길이 len만큼 일치하는지 검사
bool matchCheck(const string& prefixSrc, int prefLen, 
                const string& suffixSrc, int sufLen) {
    if (prefLen > suffixSrc.length() || sufLen > prefixSrc.length()) 
        return false;
    // prefixSrc의 [0, prefLen) vs suffixSrc의 [len-sufLen, len)
    for (int i = 0; i < prefLen && i < sufLen; i++) {
        if (prefixSrc[i] != suffixSrc[suffixSrc.length() - sufLen + i])
            return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string firstMoo, secondMoo;
    cin >> firstMoo >> secondMoo;
    
    int maxOverlap = 0;
    int len1 = firstMoo.length();
    int len2 = secondMoo.length();
    
    // 경우 1: first의 접두사 + second의 접미사
    for (int k = 1; k <= min(len1, len2); k++) {
        bool valid = true;
        for (int i = 0; i < k; i++) {
            if (firstMoo[i] != secondMoo[len2 - k + i]) {
                valid = false;
                break;
            }
        }
        if (valid) maxOverlap = max(maxOverlap, k);
    }
    
    // 경우 2: second의 접두사 + first의 접미사
    for (int k = 1; k <= min(len1, len2); k++) {
        bool valid = true;
        for (int i = 0; i < k; i++) {
            if (secondMoo[i] != firstMoo[len1 - k + i]) {
                valid = false;
                break;
            }
        }
        if (valid) maxOverlap = max(maxOverlap, k);
    }
    
    cout << maxOverlap << '\n';
    return 0;
}

더 간결한 대안 풀이

STL의 compare 메서드를 활용한 버전:

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

int findMaxEcho(const string& echoA, const string& echoB) {
    int best = 0;
    int n = echoA.size(), m = echoB.size();
    
    for (int span = 1; span <= min(n, m); span++) {
        // echoA[0:span) vs echoB[m-span:m)
        if (echoA.compare(0, span, echoB, m - span, span) == 0)
            best = max(best, span);
        // echoB[0:span) vs echoA[n-span:n)  
        if (echoB.compare(0, span, echoA, n - span, span) == 0)
            best = max(best, span);
    }
    return best;
}

int main() {
    string sound1, sound2;
    cin >> sound1 >> sound2;
    cout << findMaxEcho(sound1, sound2) << endl;
    return 0;
}

복잡도 분석

시간 복잡도: O(L²) — L은 문자열의 최대 길이(80). 각 가능한 길이 k에 대해 O(k) 비교.

공간 복잡도: O(1) — 추가 공간 없이 인덱스 연산만 수행.