首页 > 试题广场 >

平方串

[编程题]平方串

热度指数：36 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串.
牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。

输入描述:

输入一个字符串s,字符串长度length(1 ≤ length ≤ 50),字符串只包括小写字符。

输出描述:

输出一个正整数,即满足要求的平方串的长度。

示例1

输入

frankfurt

输出

算法知识视频讲解

PengWu-wp

// 转换为求两字符串公共子串的最大长度
#include <iostream>
#include <vector>
using namespace std;

int maxCommen(string &s1, string &s2) {
    int n1 = s1.size(), n2 = s2.size();
    vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
    for (int i = 1; i <= n1; ++i) {
        for (int j = 1; j <= n2; ++j) {
            if (s1[i - 1] == s2[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[n1][n2];
}

int main () {
    string s;
    cin >> s;
    int n = s.size();
    int maxLen = 0;
    for (int i = 1; i < n; ++i) {
        string s1 = s.substr(0, i);
        string s2 = s.substr(i, n - i);
        int tmp = maxCommen(s1, s2);
        maxLen = max(maxLen, tmp);
    }
    cout << maxLen * 2 << endl;
    return 0;
}

发表于 2022-10-19 22:42:21 回复(0)