《CF25E Test》

题目描述

给定 3 个字符串 s1​,s2​,s3​，试求一个字符串，使 s1​,s2​,s3​ 都是这个字符串的子串，并使这个字符串最短。输出最短字符串的长度 l。

输入格式

第一行输入一个字符串，表示 s1​。

第二行输入一个字符串，表示 s2​。

第三行输入一个字符串，表示 s3​。

输出格式

第一行输出一个正整数，表示答案 l。

显示翻译

题意翻译

输入输出样例

输入 #1复制

ab
bc
cd

输出 #1复制

4

输入 #2复制

abacaba
abaaba
x

输出 #2复制

11

说明/提示

1≤∣s1​∣,∣s2​∣,∣s3​∣≤105。

代码实现;

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string merge(const string& a, const string& b) {
    int len_a = a.length();
    int len_b = b.length();
    for (int i = min(len_a, len_b); i >= 0; --i) {
        if (a.substr(len_a - i) == b.substr(0, i)) {
            return a + b.substr(i);
        }
    }
    return a + b;
}

int main() {
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    
    vector<string> strs;
    strs.push_back(s1);
    strs.push_back(s2);
    strs.push_back(s3);
    
    vector<int> perm;
    perm.push_back(0);
    perm.push_back(1);
    perm.push_back(2); 
    int min_len = INT_MAX;
    
    do {
        string merged = merge(strs[perm[0]], strs[perm[1]]);
        merged = merge(merged, strs[perm[2]]);
        if (merged.length() < min_len) {
            min_len = merged.length();
        }
    } while (next_permutation(perm.begin(), perm.end()));
    
    cout << min_len << endl;
    
    return 0;
}