绵阳网站建设scmmwl,电子商务网站策划书3000字,wordpress 动漫网站,软件开发做平台题目描述
Catcher是MCA国的情报员#xff0c;他工作时发现敌国会用一些对称的密码进行通信#xff0c;比如像这些ABBA#xff0c;ABA#xff0c;A#xff0c;123321#xff0c;但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA-他工作时发现敌国会用一些对称的密码进行通信比如像这些ABBAABAA123321但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA-12ABBA,ABA-ABAKK,123321-51233214 。因为截获的串太长了而且存在多种可能的情况abaaab可看作是aba,或baaab的加密形式Cathcer的工作量实在是太大了他只能向电脑高手求助你能帮Catcher找出最长的有效密码串吗 输入描述: 输入一个字符串
输出描述: 返回有效密码串的最大长度
示例1
输入
复制
ABBA
输出
复制
4
方法一动态规划 可能超时
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc new Scanner(System.in); while(sc.hasNext()){ String x sc.nextLine(); int dp[][] new int[x.length()1][x.length()1]; String y new StringBuilder(x).reverse().toString(); int max0; for(int i1;ix.length();i){ for(int j1;jy.length();j){ if(x.charAt(i-1)y.charAt(j-1)){ dp[i][j] dp[i-1][j-1]1; }else{ dp[i][j] 0; } if(maxdp[i][j]) { max dp[i][j]; } } } System.out.println(max); } sc.close(); } }
方法二中心扩展法
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc new Scanner(System.in); while(sc.hasNext()){ String x sc.nextLine(); int max0; int low,high; for(int i1;ix.length()-1;i) { low i-1;highi; while(low0highx.length()x.charAt(low)x.charAt(high)) { low--; high; } max Math.max(max,high-low-1);//序列总数为偶数中心两个 low i-1;highi1; while(low0highx.length()x.charAt(low)x.charAt(high)) { low--; high; } max Math.max(max,high-low-1);//序列总数为奇数中心一个 } System.out.println(max); } sc.close(); } }
