When we calculate the longest back to text string, common method is to center diffusion method, namely, starting from the center of character, to compare both sides, check whether the equal, if it is, is to continue to check, and make the corresponding character center back to the longest text string length plus one, otherwise, the center of the end of the character palindrome examination, compared with the current the longest string of text string back, Consider whether to update the longest substring length of the entire string, and proceed to the next character.
The time complexity of this method is still O(n2)O(n^2)O(n2). The more common brute force cracking method has a good optimization, but it is not the best idea. The relevant code is as follows:
public class Solution {
private int max = 0;
private String res = "";
public String longestPalindrome(String s) {
if (s.length() == 1) { return s; }
for (int i = 0; i < s.length()-1; i++) {
checkPalindromeExpand(s,i,i);
checkPalindromeExpand(s,i,i+1);
}
return res;
}
public void checkPalindromeExpand(String s, int low, int high) {
while (low >= 0 && high < s.length()) {
if (s.charAt(low) == s.charAt(high)) {
if (high - low + 1 > max) {
max = high - low + 1;
res = s.substring(low,high+1);
}
low--; high++;
} else {
return; }}}}Copy the codeOf course, the above algorithm also has optimization space, the basic idea is as follows:
- The frequency of occurrence of a character is counted and represented by an array. When the frequency of occurrence of a character is 1, it is considered that the character may be the center point of a certain substring of a text; otherwise, it does not belong to any substring of a text
- Find the character A with frequency of 1, and see that a is the center of the single core diffusing outwardly to find the longest palindrome; If there is no palindrome, break it from the string and divide and conquer; If the palindrome exceeds the length of the record, it is saved
- Then check the palindrome from left to right, and save only when the length exceeds the record
- After the first series segmentation is completed, divide and conquer is carried out, the frequency is re-counted, and step 1 is returned
The implementation code can be used for reference: the longest loop substring length of Xiao Ma Ge
Manachar algorithm
The best method to get the length of the longest substring is Manachar algorithm, commonly known as horse-and-cart algorithm. Before we look at this algorithm, we must understand some properties of the subroutine:
-
Suppose that for a palindrome string and its center position, according to the properties of the palindrome string, from its center to both sides gradually spread to the boundary, the corresponding range of strings in each step is a palindrome string
-
If we know the central point mid of a palindrome string and its boundary range. Then, in most cases, the two points A and B that lie within the boundary and are symmetric about this central point, if there is a palindrome centered on A, then the palindrome centered on B is exactly the same as the palindrome centered on A. B =2×mid− AB =2 \times mid – ab=2×mid− A
-
The character length from the end of the palindrome string to the center of the palindrome string is the radius of the palindrome string. If the subscript of the end position is A, the subscript of the center position is ID, and the radius of the palindrome string length is len, that is, the radius is len, they have the following relationship:
To facilitate processing, combine the two cases where the string length may be odd and the string length may be even by adding a special character, such as “#”, to the left and right of each character. Add a special symbol not * at the beginning and end to ensure that the boundary is not crossed. For example, adding a “^” at the beginning and a “$” at the end can be seen in the following practice:
It follows from the above practice that since the number of # signs inserted must be equal to the number of characters plus the ^ and $characters over and over again, the total length is even + odd = odd. In this way, the length of the string can be odd, so that there is no need for a case discussion of even and odd lengths.
After preprocessing the string, define an array len that stores each character in the string as the length of the palindrome substring centered on the palindrome and the total length of the original string without special characters.
The proof method is as follows:
- After conversion, all the length of the palindrome substring is odd, so the longest length of the palindrome substring with central position subscript I is 2×len[I]−12 \times len[I] -12 ×len[I]−1
- In the palindrome string, the number of special characters is len[I], and whatever is left after the special characters are removed is the original character. Namely (2 x len – [I] 1) – len [I] = len [I] – 1 (2 \ times len [I] 1) – len [I] = len [I] 1 (2 x len – [I] 1) – len [I] = len [I] – 1
The problem turns to finding all the numbers in len[I].
Given the longest substring length of P len[P], the left boundary of the palindrome string is p-len [P], and the right boundary is P + len[P].
Suppose I have a point J to the left of the center P, whose point of symmetry is I,
- If I > len[p] + p, violent comparison usually occurs at the beginning of the solution.
- If I < len[p] + p, and len[j] < len[p] + p-i (the distance from the right boundary to I), then it is completely wrapped in a substring centered on p, there must be len[I] = len[j].
- If I = len[p] + p, and Len [j] >= len[p] + p-i, len[I] = len[j], there may be palindromic regions beyond the original P, and we still need to start from the boundary I + 1 + len[I] to compare one by one
After taking the length of the current center I, judge whether the right boundary of the palindrome region of I is greater than the original palindrome right boundary. If so, update the palindrome right boundary with center point I and right boundary I.
Solving the problem of obtaining Len array basically completes the understanding of Manachar algorithm. The relevant codes are as follows:
import java.util.Scanner;
public class Manacher {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.next();
String res = longestPalindrome(str);
System.out.println(res + ":" + res.length());
}
// Insert the character
public static String preProcess(String s) {
int n = s.length();
if (n == 0) {
return ^ "$";
}
String ret = "^";
for (int i = 0; i < n; i++)
ret = ret + "#" + s.charAt(i);
ret = ret + "# $";
return ret;
}
// The cart algorithm
public static String longestPalindrome(String str) {
String S = preProcess(str);
int n = S.length();// Keep the length of the palindrome string
int[] len = new int[n];
int center = 0, right = 0;// Preserve the right-most palindrome core and the right boundary
// Start with the first character
for (int i = 1; i < n - 1; i++) {
// Find the symmetry of I to the back core
int mirror = 2 * center - i;
if (right > i) {
// I is in the category of the right boundary, look at the length of the palindrome string at the symmetric point of I, and the length from I to the right boundary, take the two smaller ones
// Do not overflow the previous boundary, otherwise core expansion is required
len[i] = Math.min(right - i, len[mirror]);
} else {
// Go beyond the scope, core expansion
len[i] = 0;
}
// Core expansion
while (S.charAt(i + 1 + len[i]) == S.charAt(i - 1 - len[i])) {
len[i]++;
}
// See if the new index is further to the right than the previous right-most palindrome string
if (i + len[i] > right) {
// Update the core
center = i;
// Update the right borderright = i + len[i]; }}// Find the longest palindrome string through the palindrome length array
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if(len[i] > maxLen) { maxLen = len[i]; centerIndex = i; }}int start = (centerIndex - maxLen) / 2;
returnstr.substring(start, start + maxLen); }}Copy the code