如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串. 牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。
区块链毕设网qklbishe.com为您提供问题的解答
如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串.
牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。
// 转换为求两字符串公共子串的最大长度 #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; }
42:21
以上就是关于问题如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串.
牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
