9.10爱奇艺编程题「平方串」解题思路

• 平方串：

形如string s = T + T的字符串

• 目标：

对于字符串s，除去若干字符使其成为平方串，求该平方串的最大长度。

• 基本思路：

将s分成两半，求两个子串的最大子序列长度（longest common subsequence）的最大值ans，最长平方串长度就是2*ans。

const int MAXN = 50;
int c[MAXN][MAXN] = { 0 };
// s - 输入串
// 左串是s[0...(s2-1)]
// 右串是s[s2...]
int lcs(string s, int s2){
    if (s2 >= s.size())    return 0;
    int size1 = s2, size2 = s.size() - s2; for (int i = 1; i <= size1; i++){
        for (int j = 1; j <= size2; j++){
            if (s[i - 1] == s[s2 + j - 1]){
                c[i][j] = c[i - 1][j - 1] + 1;
            }
            else{
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
    }
    return c[size1][size2];
}

为了减少做LCS的次数，我先把输入串中的只出现一次的字符滤除掉，不过好像不是很必要

int main() {
    string s;
    cin >> s;
    int map[26] = { 0 };
    for (int i = 0; i < s.size(); ++i){
        map[s[i] - 'a']++;
    }
    string ns;
    for (int i = 0; i < s.size(); ++i){
        if (map[s[i] - 'a'] > 1){
            ns.push_back(s[i]);
        }
    }
    int ans = 0;
    for (int i = 1; i < ns.size(); i++){
        int x = lcs(ns, i);
        if (x > ans)    ans = x;
    }
    cout << ans * 2 << endl;
    //system("pause");
    return 0;
}