16925번 문자열 추측

https://www.acmicpc.net/problem/16925

# 문자열 # find # 접두사 # 접두 # 접미사 # 접미 # prefix # suffix # 구현 # 복습 # 처리 # 필수 # 코테

처음에는 어떻게 구현할지 몰랐다.

알고보니, 문자열의 길이가 n - 1인 문자열 a, b를 활용하는 문제이다.

완성된 문자열은

1. a + b의 마지막 문자(a가 접두사, b가 접미사)

2. b + a의 마지막 문자(a가 접미사, b가 접두사)

위의 2개 중 하나이다.

그리고, 처리해줘야 할 것은 접두사, 접미사 모두 해당할 때인데

이 경우에는 무조건 하나의 경우밖에 없다.

바로 어떠한 문자열 str이 이미 접두사로 사용된 경우다.

abab일 경우, 접두사로 ab, 접미사로 ab가 있을 것이고,

입력시에 ab가 2번 입력될 것이다.

처음의 ab는 접두사로 인식하겠지만

두 번째의 ab는 이미 접두사로 인식됐으므로, 접미사로 해야한다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
vector<string> input, v;
set<string> prefix_set; // 접두사 저장
 
// 접두사
bool isPrefix(string original, string part)
{
    if (original.find(part) == 0) {
        return true;
    }
    return false;
}
 
// 접미사
bool isSuffix(string original, string part)
{
    /*
    original이 ababa이고, part가 ba일 경우,
    original.find(part)의 값은 1이다.
    따라서, original.length() - part.length()의 값인 3과는 다르다.
    이를 위해, find에서 탐색 위치를 지정해줘야 하는데, original의 끝 부분에서 part의 길이만큼 빼서, 
    그 부분부터 탐색을 시작하면 된다.
    */
    if (original.find(part, original.length() - part.length()) == original.length() - part.length()) {
        return true;
    }
    return false;
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d", &n);
 
    string s;
    for (int i = 0; i < 2 * n - 2; i++) {
        cin >> s;
        input.push_back(s);
 
        // 길이가 n-1인 문자열만 v에 push
        if (s.length() == n - 1) {
            v.push_back(s);
        }
    }
 
    string s1 = v[0] + v[1][v[1].length() - 1];
    string s2 = v[1] + v[0][v[0].length() - 1];
 
    vector<string> sentence = { s1, s2 };
 
    for (auto i : sentence) { // 완성 문자열들
        string ans = "";
        prefix_set.clear();
 
        for (auto input_string : input) {
 
            // 접두사라면
            if (isPrefix(i, input_string)) {
 
                // 아직 접두사로 input_string이 나온 적이 없다면
                if (!prefix_set.count(input_string)) {
                    prefix_set.insert(input_string);
                    ans += "P";
                }
 
                // 이미 input_string이 사용된 접두사라면
                else {
                    // 접미사로 취급
                    ans += "S";
                }
            }
 
            // 접두사가 아니라면
            else {
 
                // 접미사라면
                if (isSuffix(i, input_string)) {
                    ans += "S";
                }
            }
        }
 
        // 완성된 ans의 문자열 길이 비교
        if (ans.length() == 2 * n - 2) {
            cout << i << "\n" << ans << "\n";
            break;
        }
    }
 
    return 0;
}