最长公共包含串题解

思路：数据量很小直接暴力枚举24种拼接方法，每种拼接方法合并时用相关的find函数找最长的公共前后缀即可，另外注意 size_t 和 int 比较的坑

/*find是找子字符串出现的首个位置,rfind是找子字符串出现的最后一个位置
find_first_of是找子字符串中任意一个字符出现的首个位置,find_last_of是找子字符串中任意一个字符出现的末尾位置
由长到短暴力枚举最长公共前后缀即可
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s[4];

int a[24][4] = {
    {0, 1, 2, 3},
    {0, 1, 3, 2},
    {0, 2, 1, 3},
    {0, 2, 3, 1},
    {0, 3, 1, 2},
    {0, 3, 2, 1},
    {1, 0, 2, 3},
    {1, 0, 3, 2},
    {1, 2, 0, 3},
    {1, 2, 3, 0},
    {1, 3, 0, 2},
    {1, 3, 2, 0},
    {2, 0, 1, 3},
    {2, 0, 3, 1},
    {2, 1, 0, 3},
    {2, 1, 3, 0},
    {2, 3, 0, 1},
    {2, 3, 1, 0},
    {3, 0, 1, 2},
    {3, 0, 2, 1},
    {3, 1, 0, 2},
    {3, 1, 2, 0},
    {3, 2, 0, 1},
    {3, 2, 1, 0},
};

int unite() {
    int ans = 40;
    for (int i = 0; i < 24; ++i) {
        string t = s[a[i][0]];
        for (int j = 1; j < 4; ++j) {
            string nex = s[a[i][j]];
            //cout << t << ' ' << nex << endl;
            if (t.find(nex) != string::npos)
                continue;
            else {
                int pos = 0;
                int len = min((int)t.size(), (int)nex.size());
                for (int k = len; k >= 1; --k) {
                    string temp = nex.substr(0, k);
                    if (t.rfind(temp) == t.size() - k) {
                        pos = k;
                        break;
                    }
                }
                t += nex.substr(pos);
            }
        }
        // cout << t.size() << endl;
        ans = min(ans, (int)t.size());
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    for (int i = 0; i < 4; ++i)
        cin >> s[i];
    cout << unite() << endl;
    system("pause");
    return 0;
}