如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串.
牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。
输入一个字符串s,字符串长度length(1 ≤ length ≤ 50),字符串只包括小写字符。
输出一个正整数,即满足要求的平方串的长度。
frankfurt
4
def max1(s1,s2): lens=[[0]*(len(s2)+1) for _ in range(len(s1)+1)] for i in range(1,len(s1)+1): for j in range(1,len(s2)+1): if s1[i-1]==s2[j-1]: lens[i][j]=lens[i-1][j-1]+1 else: lens[i][j]=max(lens[i-1][j],lens[i][j-1]) return lens[len(s1)][len(s2)] s=raw_input() max2=0 for i in range(1,len(s)): max2=max(max1(s[:i],s[i:]),max2) print max2*2
s = input() c = [] for index in range(1, len(s)): a = s[:index] b = s[index:] arr = [[0 for i in range(len(b) + 1)] for j in range(len(a) + 1)] num = 0 for i in range(len(a)): for j in range(len(b)): if a[i] == b[j]: arr[i+1][j+1] = arr[i][j] + 1 num = max(num, arr[i+1][j+1]) else: arr[i+1][j+1] = max(arr[i+1][j], arr[i][j+1]) num = max(num, arr[i+1][j+1]) c.append(num) print(max(c)*2)动态规划求解最长公共子序列,将给定的字符串遍历截断为两部分,然后求得的最长公共子序列的长度的两倍就是我们需要的输出
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @author wylu */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); int res = 0; for (int i = 1; i < s.length(); i++) { res = Math.max(res, lcs(s.substring(0, i), s.substring(i))); } System.out.println(res * 2); } //求s1和s2的最长公共子序列的长度 private static int lcs(String s1, String s2) { //dp[i + 1][j + 1]: 以s1[i]、s2[j]为结尾的最长公共子序列的长度 int[][] dp = new int[s1.length() + 1][s2.length() + 1]; for (int i = 0; i < s1.length(); i++) { for (int j = 0; j < s2.length(); j++) { if (s1.charAt(i) == s2.charAt(j)) { dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]); } } } return dp[s1.length()][s2.length()]; } }
本套3道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions),牛客网上的其他题目解答也在持续更新。
本道题考察最长公共子序列,在原序列任意点断开,分为左右两个序列,这两个序列的最长公共子序列就是以此点为中点的最长平方串,遍历所有断开的点及找到最长平方串。
#include #include #include #include using namespace std; int main() { string sequence; cin >> sequence; int len = sequence.length(); int maxlen = 0; for (int k = 1; k < len; k++) { int **DP = new int*[k]; for (int i = 0; i < k; i++) { DP[i] = new int[len - k]; memset(DP[i], 0, sizeof(int)*(len - k)); } DP[0][0] = sequence[0] == sequence[k] ? 1 : 0; for (int i = 1; i < k; i++) { DP[i][0] = sequence[i] == sequence[k] ? 1 : DP[i - 1][0]; } for (int i = 1; i < len - k; i++) { DP[0][i] = sequence[0] == sequence[k + i] ? 1 : DP[0][i - 1]; } for (int i = 1; i < k; i++) { for (int j = 1; j < len - k; j++) { DP[i][j] = sequence[i] == sequence[k + j] ? DP[i - 1][j - 1] + 1 : DP[i - 1][j - 1]; DP[i][j] = max(DP[i][j], DP[i - 1][j]); DP[i][j] = max(DP[i][j], DP[i][j - 1]); } } maxlen = max(maxlen, DP[k - 1][len - k - 1]); for (int i = 0; i < k; i++) { delete[] DP[i]; } delete[] DP; } cout << maxlen * 2 << endl; return 0; }
#include <bits/stdc++.h> using namespace std; int F(string a, string b){ int n=a.length(), m=b.length(); int dp[n+1][m+1]; memset(dp, 0, sizeof(dp)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i]!=b[j]) dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); else dp[i+1][j+1] = dp[i][j] + 1; return dp[n][m]; } int main(){ string s; cin>>s; int Max = 0; for(int i=1;i<s.length()-1;i++) Max = max(Max, 2*F(s.substr(0,i), s.substr(i))); printf("%d\n", Max); return 0; }
s = input().strip() def lcs(a, b): dp = [[0 for i in range(len(b) +1)] for i in range(len(a) + 1)] for i in range(1, len(a) + 1): for j in range(1, len(b) + 1): 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[len(a)][len(b)] result = 0 for i in range(1, len(s) - 1): result = max(result, lcs(s[:i], s[i:])) print(result * 2)
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int max = Integer.MIN_VALUE; for(int i = 0; i < str.length(); i++){ max = Math.max(max, lcs(str.substring(0, i), str.substring(i))); } System.out.println(2 * max); } public static int lcs(String str1, String str2) { int[][] dp = new int[str1.length() + 1][str2.length() + 1]; for(int i = 0; i < str1.length(); i++) for(int j = 0; j < str2.length(); j++) dp[i + 1][j + 1] = str1.charAt(i) == str2.charAt(j) ? dp[i][j] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]); return dp[str1.length()][str2.length()]; } }
import java.util.*; public class Main{ public static void main(String[] args){ try(Scanner in = new Scanner(System.in)){ String s = in.nextLine(); int max = 0; for(int i = 1;i < s.length();i++){ max = Math.max(max,helper(s.substring(0,i),s.substring(i))); } System.out.println(2 * max); } } public static int helper(String s1,String s2){ int[][] dp = new int[s1.length() + 1][s2.length() + 1]; for(int i = 0;i < s1.length();i++){ for(int j = 0;j < s2.length();j++){ dp[i + 1][j + 1] = s1.charAt(i) == s2.charAt(j) ? dp[i][j] + 1 : Math.max(dp[i][j + 1],dp[i + 1][j]); } } return dp[s1.length()][s2.length()]; } }
//平方串
#include<iostream>
using namespace std;
#include <string>
#define max(a,b) (((a) > (b)) ? (a) : (b))
//测试用例:
//fjkjsakljflkjakljjfiwoqjfioq wfoiqwjfiojq
//
//对应输出应该为 :
//
//16
//
//你的输出为 :
//
// 18
int findMaxCom(string a_, string b_)
{
int dp[51][51] = { 0 };
int ret = 0;
for (int i = 1; i <= a_.size();i++)
{
for (int j = 1; j <= b_.size();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]);
}
//ret = (ret > dp[i][j]) ? ret : dp[i][j];
}
}
ret=dp[a_.size()][b_.size()];
return ret;
}
int main()
{
string str;
char temp[50];
cin >> str;
int ret = 0;
string a,b;
for (int i = 0; i < str.size(); i++)
{
a = str.substr(0, i), b = str.substr(i, str.size()-i);
int max_com_len = findMaxCom(a,b);
ret = ret>max_com_len ? ret : max_com_len;
}
cout << ret * 2 << endl;
return 0;
}
i,j =1
开始用if (a_[i-1]==b_[j-1])
#include<iostream>#include<string>usingnamespacestd;intMaxLength(string s,ints2)//从s2位置把字符串切开{intc[50][50]={0};if(s2 >= s.size()) return0;intsize1 = s2, size2 = s.size() - s2; for(inti = 1; i <= size1; i++){for(intj = 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]);}}}returnc[size1][size2];}intmain(){string str;cin>>str;intmax=0;intsize=str.size();for(inti=0;i<size;i++){inttmp;tmp=MaxLength(str,i);if(tmp>max)max=tmp;}cout<<2*max;return0;}
import java.util.*; public class Main { public static void main(String[]args){ Scanner in=new Scanner(System.in); String s=in.next(); if(s.length()==1) System.out.println(0); else{ int res=0,i,n=s.length(); for(i=0;i+1<n;i++) res=Math.max(res,maxLen(s.substring(0,i+1),s.substring(i+1))); System.out.println(res); } } public static int maxLen(String a,String b){ int len1=a.length(),len2=b.length(),i,j; int [][]dp=new int[len1+1][len2+1]; for(i=1;i<=len1;i++) for(j=1;j<=len2;j++) dp[i][j]=(a.charAt(i-1)==b.charAt(j-1) ?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1])); return dp[len1][len2]*2; } }
def MaxS(s,l,n): #l为分割线 dp = [[0]*(l+1) for _ in range(n-l+1)] M = 0 for i in range(n-l): for j in range(l): if s[j]==s[l+i]: dp[i+1][j+1]=dp[i][j]+1 else: dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]) M = max(M,dp[i+1][j+1]) return M s = input() n = len(s) R = 0 mid = int(n/2) flag = 1 for i in range(1,n): if min(mid,n-mid)<=R: break M = MaxS(s,mid,n) R = max(M,R) mid += flag*i flag = -flag print(2*R)切一刀,然后动态规划,切刀时优先从中间切,方便剪枝,速度一流
import java.util.Scanner; /** * @Author: coderjjp * @Date: 2020-05-15 8:12 * @Description: 平方串 * @version: 1.0 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); String l, r; int ans = 0; for (int i = 1; i < s.length(); i++){ l = s.substring(0, i); r = s.substring(i); int dp[][] = new int[l.length()+1][r.length()+1]; for (int m = 1; m <= l.length(); m++) for (int n = 1; n <= r.length(); n++){ if (l.charAt(m-1) == r.charAt(n - 1)){ dp[m][n] = dp[m-1][n-1] + 1; }else { dp[m][n] = Math.max(dp[m-1][n], dp[m][n-1]); } } ans = Math.max(ans, dp[l.length()][r.length()]); } System.out.println(2 * ans); } }
#include<iostream> #include<vector> #include<algorithm> using namespace std; int LCS(string s1, string s2){ const int maxn = 60; int dp[maxn][maxn]; for(int i=0; i < maxn; i++){ dp[i][0] = 0; dp[0][i] = 0; } for(int i = 0; i < s1.size(); i++){ for(int j = 0; j < s2.size(); j++){ if(s1[i] == s2[j]){ dp[i+1][j+1] = dp[i][j] + 1; }else{ dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); } } } return dp[s1.size()][s2.size()]; } int main() { string s; cin >> s; int result = 0; for(int i=0; i < s.size(); i++){ string s1 = s.substr(0, i+1); string s2 = s.substr(i+1, s.size()-(i+1)); int temp = LCS(s1, s2); result = max(temp, result); // cout << s1 << " " << s2 << " " << result << endl; } cout << result*2; return 0; }
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int LCS(string s1, string s2) { const int len1 = s1.length(), len2 = s2.length(); vector<vector<int>> lcs(len1 + 1, vector<int>(len2 + 1, 0)); for (int i = 0; i < len1; ++i) for (int j = 0; j < len2; ++j) { if (s1[i] == s2[j]) lcs[i + 1][j + 1] = lcs[i][j] + 1; else lcs[i + 1][j + 1] = max(lcs[i][j + 1], lcs[i + 1][j]); } return lcs[len1][len2]; } int main() { string s; cin >> s; int max_len = 0; for(size_t i = 1; i < s.length() - 1; ++i) max_len = max(max_len, 2 * LCS(s.substr(0, i), s.substr(i))); cout << max_len << endl; }
//递归,果然超时了。分成两个子序列,两个序列求最长公共子序列的问题,动态规划 import java.util.*;// 递归 public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ CAL(sc); } } public static void CAL(Scanner sc){ String s=sc.next(); int i=0; System.out.println(DIGUI(s,0)); } public static int DIGUI(String s,int n){ if (PanDu(s)) { int jj=s.length(); return s.length(); } if(s.length()-1<n) { return 0; } return Math.max(DIGUI(s.substring(0,n)+s.substring(n+1),n),DIGUI(s,n+1)) ; } public static boolean PanDu(String s){ if(s.length()%2==1) return false; else{ String s1=s.substring(0,s.length()/2); String s2=s.substring(s.length()/2); if(s1.equals(s2)) return true; else return false; } } } //动态规划 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ CAL(sc); } } public static void CAL(Scanner sc){ String s=sc.next(); int n=s.length(); int R=0; for(int i=0;i<n;i++) { int t=Hel(s.substring(0,i),s.substring(i)); if (t>R) { R=t; } } System.out.println(R*2); } public static int Hel(String s1,String s2) { //求s1和s2最长公共子序列 int[][] dp=new int[s2.length()+1][s1.length()+1]; for(int i=1;i<=s2.length();i++) { for(int j=1;j<=s1.length();j++) { if(s2.charAt(i-1)==s1.charAt(j-1)) { dp[i][j]=dp[i-1][j-1]+1; } else { dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); } } } return dp[s2.length()][s1.length()]; } }