题目分析

给定一个字符串$S$（$|S| \le 80$），要求找出最长的强大子序列的长度。强大子序列定义为可以由某个字符串$T'$重复$k$次（$k \ge 2$）拼接而成的子序列。

核心观察

设最长强大子序列为$T$，它可以表示为$T = \underbrace{T' + T' + \cdots + T'}_{k \text{ 次}}$，则$k \cdot |T'| = |T| \le |S| \le 80$。

由于$|S|$很小，$k$和$|T'|$不能同时很大。我们可以根据$k$的大小分类讨论：

• 当$k < 5$时，需要考虑$k=2$和$k=3$的情况（$k=4$可以被$k=2$覆盖，因为$T = (T'+T')+(T'+T')$）
• 当$k \ge 5$时，$|T'| \le \frac{|S|}{5} \le 16$，长度很小

算法设计

情况1：$k=2$

当$T = T' + T'$时，我们需要在$S$中找到一个子序列，它由两个相同的子序列拼接而成。

方法：将$S$分成两部分$S = S_1 + S_2$（在某个位置分割），然后计算$S_1$和$S_2$的最长公共子序列（LCS）长度$L$。那么$2L$就是一个候选答案（因为我们可以从$S_1$中取$T'$，从$S_2$中取另一个$T'$）。

复杂度：分割点有$O(|S|)$个，每次LCS计算$O(|S|^2)$，总复杂度$O(|S|^3) = O(80^3)$。

情况2：$k=3$

类似地，将$S$分成三部分$S = S_1 + S_2 + S_3$，计算三个字符串的最长公共子序列长度$L$，则$3L$是候选答案。

复杂度：分割点有$O(|S|^2)$种，每次LCS3计算$O(|S|^3)$，总复杂度$O(|S|^5)$。由于$|S| \le 80$，$80^5 \approx 3.2 \times 10^9$，需要优化。

优化分析：对于固定的分割$(|S_1|, |S_2|, |S_3|)$，LCS3的计算复杂度为$|S_1| \cdot |S_2| \cdot |S_3|$。由均值不等式，当$|S_1| = |S_2| = |S_3| = \frac{|S|}{3}$时乘积最大，为$\frac{|S|^3}{27}$。分割点数量为$\binom{|S|-1}{2} \le \frac{|S|^2}{2}$，因此总复杂度不超过$\frac{|S|^5}{54}$，常数$\frac{1}{54}$很小，实际可行。

情况3：$k \ge 5$

此时$|T'| \le \frac{|S|}{5} \le 16$。关键观察：如果将$S$分成5个长度尽可能相等的部分，那么$T'$必然是其中至少一个部分的子序列（鸽巢原理）。

算法步骤：

1. 将$S$分成5段，每段长度$\lfloor \frac{|S|}{5} \rfloor$或$\lceil \frac{|S|}{5} \rceil$
2. 对每一段，枚举它的所有非空子序列（最多$2^{16} = 65536$种）
3. 对每个子序列$T'$，在$S$中贪心地匹配，计算最多能重复多少次
4. 如果重复次数$\ge 5$，更新答案

复杂度：$5 \times 2^{|S|/5} \times |S| = O(5 \cdot 2^{16} \cdot 80) \approx 2.6 \times 10^7$，可行。

最终复杂度

总时间复杂度：$O(\frac{|S|^5}{54} + 5 \cdot 2^{|S|/5} \cdot |S|)$，对于$|S|=80$完全可行。

代码实现

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

string s;
int n;
int ans = 0;

// 计算两个字符串的最长公共子序列长度
int lcs2(const string& a, const string& b) {
    int la = a.size(), lb = b.size();
    vector<vector<int>> dp(la + 1, vector<int>(lb + 1, 0));
    for (int i = 1; i <= la; i++) {
        for (int j = 1; j <= lb; j++) {
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[la][lb];
}

// 计算三个字符串的最长公共子序列长度
int lcs3(const string& a, const string& b, const string& c) {
    int la = a.size(), lb = b.size(), lc = c.size();
    vector<vector<vector<int>>> dp(la + 1, vector<vector<int>>(lb + 1, vector<int>(lc + 1, 0)));
    for (int i = 1; i <= la; i++) {
        for (int j = 1; j <= lb; j++) {
            for (int k = 1; k <= lc; k++) {
                if (a[i - 1] == b[j - 1] && b[j - 1] == c[k - 1])
                    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                else
                    dp[i][j][k] = max({dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]});
            }
        }
    }
    return dp[la][lb][lc];
}

// 处理 k = 2 的情况
void solve_k2() {
    for (int split = 1; split < n; split++) {
        string s1 = s.substr(0, split);
        string s2 = s.substr(split);
        int len = lcs2(s1, s2);
        ans = max(ans, len * 2);
    }
}

// 处理 k = 3 的情况
void solve_k3() {
    for (int split1 = 1; split1 < n; split1++) {
        for (int split2 = split1 + 1; split2 < n; split2++) {
            string s1 = s.substr(0, split1);
            string s2 = s.substr(split1, split2 - split1);
            string s3 = s.substr(split2);
            int len = lcs3(s1, s2, s3);
            ans = max(ans, len * 3);
        }
    }
}

// 处理 k >= 5 的情况
void solve_kge5() {
    // 将 s 分成 5 段，长度尽量平均
    vector<string> parts;
    int base = n / 5;
    int rem = n % 5;
    int start = 0;
    for (int i = 0; i < 5; i++) {
        int segLen = base + (i < rem ? 1 : 0);
        parts.push_back(s.substr(start, segLen));
        start += segLen;
    }

    // 枚举所有可能的 T'（是某一段的子序列）
    for (int idx = 0; idx < 5; idx++) {
        string part = parts[idx];
        int m = part.size();
        // 枚举 part 的所有非空子序列
        for (int mask = 1; mask < (1 << m); mask++) {
            string t;
            for (int i = 0; i < m; i++) {
                if (mask >> i & 1) t.push_back(part[i]);
            }
            // 贪心匹配，计算 t 在 s 中最多能重复多少次
            int cnt = 0;
            int p = 0;
            for (char ch : s) {
                if (ch == t[p]) {
                    p++;
                    if (p == t.size()) {
                        cnt++;
                        p = 0;
                    }
                }
            }
            if (cnt >= 5) {
                ans = max(ans, (int)t.size() * cnt);
            }
        }
    }
}

int main() {
    cin >> s;
    n = s.size();
    ans = 0;

    solve_k2();   // k = 2
    solve_k3();   // k = 3
    solve_kge5(); // k >= 5

    cout << ans << endl;
    return 0;
}

正确性证明

1. 情况$k=2,3$：通过枚举所有分割点，LCS保证了两个/三个子序列完全相同，且每个子序列来自$S$的不同部分，因此拼接后是$S$的子序列。

2. 情况$k\ge5$：由于$T'$长度$\le \frac{|S|}{5}$，将$S$分成5段后，由鸽巢原理，$T'$必然完整地出现在某一段的子序列中。枚举所有可能的$T'$后，贪心匹配能求出最大重复次数，保证了正确性。

3. 覆盖所有情况：任何强大子序列对应某个$k\ge2$，必然落入$k=2,3$或$k\ge5$的讨论范围（$k=4$被$k=2$覆盖）。