Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to realize the longest text string of Java". The content of the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to achieve the longest text string of Java".

/ * * longest palindrome substring * * famous Manacher algorithm O (N) time O (N) space * / public class LongestPalindrome {public static void main (String [] args) {LongestPalindrome lp = new LongestPalindrome (); System.out.println (lp.longestPalindrome ("babcbabcbaccba")) / / qgjjgq} / * an O (N) algorithm (Manacher) * / / Transform S into T. / / For example, S = "abba", T = "^ # a * * bounded breadth * * $". / / ^ and $signs are sentinels appended to each end to avoid bounds checking// String preProcess (String s) {/ / int n = s.length (); / / if (n = = 0) return "^ $"; / String ret = "^"; / / for (int I = 0; I

< n; i++)// {// ret += "#" + s.substring(i, i + 1);// }//// ret += "#$";// return ret;// }// public String longestPalindrome(String s) {// String T = preProcess(s);// System.out.println(T);// int length = T.length();// int[] p = new int[length];// int C = 0, R = 0;//// for (int i = 1; i < length - 1; i++)// {// int i_mirror = C - (i - C);// int diff = R - i;// if (diff >

= 0) / / the current I is between C and R, you can use the symmetry attribute of palindromes / / {/ / if (p [I _ mirror])

< diff)//i的对称点的回文长度在C的大回文范围内部// { p[i] = p[i_mirror]; }// else// {// p[i] = diff;// //i处的回文可能超出C的大回文范围了// while (T.charAt(i + p[i] + 1) == T.charAt(i - p[i] - 1))// { p[i]++; }// C = i;// R = i + p[i];// }// }// else// {// p[i] = 0;// while (T.charAt(i + p[i] + 1) == T.charAt(i - p[i] - 1))// { p[i]++; }// C = i;// R = i + p[i];// }// }//// int maxLen = 0;// int centerIndex = 0;// for (int i = 1; i < length - 1; i++) {// if (p[i] >

MaxLen) {/ / maxLen = p [I]; / / centerIndex = iPlacter /} / / return s.substring ((centerIndex-1-maxLen) / 2, (centerIndex-1-maxLen) / 2 + maxLen); / /} / * 3. The central extension method because the palindrome string is symmetrical on the central axis, so if we start from the subscript I and use two pointers to expand to both sides of I to determine whether it is equal or not, then we only need to do this operation on the subscript 0 to nmur1. You can find the longest palindrome substring. However, it should be noted that palindromes can be divided into two types: "abcba" and "abba", so you need to make a judgment when writing the code. Let the function int Palindromic (string & s, int I, int j) be the length of the palindrome string extending from subscript I and j to both sides, then the substring length of odd palindromes and even palindromes can be obtained by calling this function int lenOdd = Palindromic (str, I, I) and int lenEven = Palindromic (str, I, j) twice. Next, compare the maximum values in lenOdd and lenEven with the current maximum value max. One advantage of this approach is that the time complexity is O (N2) and no extra space is required. * / public String longestPalindrome (String s) {/ / if (s.isEmpty ()) {/ / return null;//} / / if (s.length () = = 1) {/ / return / s.substring / / String longest = s.substring (0,1); / / for (int I = 0; I

< s.length(); i++) {// // get longest palindrome with center of i// String tmp = helper(s, i, i);// if (tmp.length() >

Longest.length () {/ / longest = tmp;//} / get longest palindrome with center of i, iTun1Universe / tmp = helper (s, I, iTun1); / / if (tmp.length () > longest.length ()) {/ / longest = tmp / /} / /} / return longest;//} / Given a center, either one letter or two letter,// Find longest palindrome// public static String helper (String s, int begin, int end) {/ / while (begin > = 0 & & end)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.