小易得到了一个仅包含大小写英文字符的字符串,该字符串可能不是回文串。(“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串,“asds”就不是回文串。)
小易可以在字符串尾部加入任意数量的任意字符,使其字符串变成回文串。
现在请你编写一个程序,程序要能计算出小易可以得到的最短回文串。
小易得到了一个仅包含大小写英文字符的字符串,该字符串可能不是回文串。(“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串,“asds”就不是回文串。)
小易可以在字符串尾部加入任意数量的任意字符,使其字符串变成回文串。
现在请你编写一个程序,程序要能计算出小易可以得到的最短回文串。
一行包括一个字符串。
一行包括一个字符串,代表答案。
noon
noon
noo
noon
helloworld
helloworldlrowolleh
逆序
原串,寻找 前缀
,简单易懂 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); // 逆序原字符串 String reverse = new StringBuffer(s).reverse().toString(); String ans = ""; int len = Integer.MAX_VALUE; if(judge(s)) { System.out.println(s); } else { for(int i=0;i<reverse.length();i++){ // 寻找r对应s的前缀 /** i s(YCiC) r(CiCY)的前缀 0 YCiC no 1 CiC yes:CiC CiC后追加(Y) Y的index=r.length()-i */ if(reverse.startsWith(s.substring(i))){ String tmp = s+reverse.substring(reverse.length()-i); if (tmp.length() < len) { len = tmp.length(); ans = tmp; } // 为什么不直接输出呢?因为可能会有多个输出,我要输出最短的那个 // System.out.println(s+reverse.substring(reverse.length()-i)); } } System.out.println(ans); } } public static boolean judge(String s) { int left = 0, right = s.length() - 1; while(left <= right) { if(s.charAt(left) == s.charAt(right)) { left++; right--; } else { return false; } } return true; } }