Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 202;

string s, p;
string ans;

int n;
int L;

int cntP[N], cntS[N];

int memo[N][N][N];

bool preCheck() {
    for (int i = 0; i < 26; ++i) cntP[i] = 0;
    for (int i = 0; i < L; ++i)
        ++cntP[p[i] - 'a'];
    for (int c = 0; c < 26; ++c) if (cntS[c] != 0)
        if (cntP[c] == 0 || cntS[c] % cntP[c] != 0 || cntS[c] / cntP[c] != (n / L)) return 0;
    return 1;
}

bool dp(int i, int j, int match) {
    if (match >= L) match -= L;
    int &ans = memo[i][j][match];
    if (ans != -1) return ans;
    if (i > j) return ans = match == 0;
    ans = 0;
    if (p[match] == s[i]) ans = dp(i + 1, j, match + 1);
    if (ans) return ans;
    if (i + L - 1 <= j) {
        for (int k = i + L - 1; k <= j; k += L) {
            ans |= dp(i, k, 0) && dp(k + 1, j, match);
            if (ans) break;
        }
    }
    return ans;
}

bool check() {
    if (!preCheck()) return 0;
    L = p.length();
    for (int i = 0; i <= n; ++i) for (int j = max(0, i - 1); j <= n; ++j) for (int k = 0; k <= L; ++k) memo[i][j][k] = -1;
    return dp(0, n - 1, 0);
}

void solve() {
    for (int i = 0; i + L <= n; ++i) {
        p = s.substr(i, L);
        if (check()) {
            if (ans == "")
                ans = p;
            else
                ans = min(ans, p);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> s;
    n = s.length();
    for (int i = 0; i < n; ++i) ++cntS[s[i] - 'a'];
    for (int i = 1; i <= n; ++i) if (n % i == 0) {
        L = i;
        solve();
        if (ans != "") break;
    }
    cout << ans << endl;
    return 0;
}