華為機試-字符串運用密碼截取

2019-11-06 06:23:02

字體：大中小

來源：轉載

供稿：網友

題目描述 Catcher是MCA國的情報員，他工作時發現敵國會用一些對稱的密碼進行通信，比如像這些ABBA，ABA，A，123321，但是他們有時會在開始或結束時加入一些無關的字符以防止別國破解。比如進行下列變化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因為截獲的串太長了，而且存在多種可能的情況（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量實在是太大了，他只能向電腦高手求助，你能幫Catcher找出最長的有效密碼串嗎？

輸入描述: 輸入一個字符串

輸出描述: 返回有效密碼串的最大長度

輸入例子: ABBA

輸出例子: 4

代碼

import java.util.Scanner;public class LongestPalindrome { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); while(sc.hasNext()) { String key=sc.next(); System.out.PRintln(longestPalindrome(key)); } sc.close(); } public static int longestPalindrome(String key) { int len=key.length(); int i; int mx = 0; int id=0; StringBuffer sb=new StringBuffer(); for(int j=0;j<len;j++) { sb.append("#"); sb.append(key.charAt(j)); } sb.append("#"); char keys[]=sb.toString().toCharArray(); int n=sb.length(); int p[]=new int[n]; for(int j=0;j<n;j++) p[j]=0; for(i=1; i<n; i++) { if( mx > i ) p[i] =Math.min(p[2*id-i], mx-i ); else p[i] = 1; for(; (((i-p[i]>=0)&&(i+p[i]<n))&&(keys[i+p[i]] == keys[i-p[i]])); p[i]++) ; if( p[i] + i > mx ) { mx = p[i] + i; id = i; } } mx=0; for(int j=0;j<n;j++) { if(p[j]>mx) mx=p[j]; } return mx-1; }}

上一篇：NSWindow支持Drag-and-Drop

下一篇：MASM32編寫的程序在Windows 7，10下運行正常，但在Win XP下運行時只聞其聲不見其形的故障