What is a palindrome string?
That is, the forward reading and reverse reading are the same strings. For example, strings like aba, abba, and cdc are all palindrome strings.
Brute force method to find the longest palindrome substring
What this diagram means is that we need to get each number on the right and then match it one by one with the number on the left.
Let’s take a look at the java implementation code
package com.pxx;
/**
* Created by Administrator on 2023/9/11.
*/
public class Test2 {
public static String longestPalindrome(String s) {
if (s == null) {
return null;
}
//The longest one is from the far right. The further you go in, the shorter it becomes.
for (int len = s.length(); len >= 1; len--) {
//Here i + len ensures that the length of each palindrome string is within the length of the entire string.
for (int start = 0; start + len <= s.length(); start + + ) {
if (isPalindrome(s,start,start + len - 1)) {
return s.substring(start,start + len);
}
}
}
//If there is no result, return an empty string
return "";
}
//Directly determine whether it is a palindrome number
private static boolean isPalindrome(String s,int left,int right) {
while (left < right & amp; & amp; s.charAt(left) == s.charAt(right)) {
left + + ;
right--;
}
//If it is a palindrome number, it will definitely cause left >= right. In some cases, the left == right program has ended.
return left >= right;//If it is true, it is a palindrome string, if it is false, it is not a palindrome string
}
public static void main(String[] args) {
String res = longestPalindrome("abcdzdcab");
System.out.println(res);
}
}
The following is the c language code implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Determine whether it is a palindrome string
bool isPalindrome(const char* s, int left, int right) {
while (left < right & amp; & amp; s[left] == s[right]) {
left + + ;
right--;
}
return left >= right;
}
// Find the longest palindrome substring
const char* longestPalindrome(const char* s) {
if (s == NULL) {
return NULL;
}
for(int len = strlen(s); len >= 1; len--) {
for(int start = 0; start + len <= strlen(s); start + + ) {
if(isPalindrome(s,start,start + len - 1)) {
char* result = (char*)malloc(sizeof(char) * (start + len));
strncpy(result, s + start, start + len - 2);
result[start + len] = '\0';
return result;
}
}
}
return "";
}
int main() {
const char* input = "abcdzdcab";
const char* result = longestPalindrome(input);
printf("Input: %s\
", input);
printf("Longest palindrome: %s\
", result);
free((void*)result); // Release dynamically allocated memory
return 0;
}
The time complexity of the above algorithm is O(n^3)
Enumeration based on the center point to find the longest substring
Implementation principle
The above is a general implementation. Specifically, it depends on odd-numbered palindrome strings or even-numbered palindrome strings.
Analysis of the implementation principle of the odd part code
Analysis of the implementation principle of the even numbered part of the code
The following is the java code implementation
public class Enumeration {
//Main function
//Get the longest palindrome string in the string
public static String longestPolindrom(String s) {
//security check
if(s == null) {
return null;
}
//Define a string we need to return
String longest = "";
//Loop through the entire string and check
for(int i = 0; i < s.length(); i + + ) {
//Here is the search for the odd part
String oddPolindrome = getPolindromeFrom(s,i,i);//As analyzed before, odd numbers are actually fixed at one point and spread out left and right. Here is i
//Determine whether to replace the obtained palindrome string or not
if (longest.length() < oddPolindrome.length()) {//If it is less than the returned value, replace it because we want to find the longest one
longest = oddPolindrome;//replace this string directly
}
//Here is the search for even strings
String evenPolindrome = getPolindromeFrom(s,i,i + 1);//An even string cannot fix a point
if (longest.length() < evenPolindrome.length()) {
longest = evenPolindrome;
}
}
\t\t
//Return after the above loop is completed
return longest;
\t\t
}
//Get the palindrome string
public static String getPolindromeFrom(String s, int left, int right) {
//Double pointers, a double pointer facing each other
while (left >= 0 & amp; & amp; right < s.length()) {
if (s.charAt(left) != s.charAt(right)) {
break;//break first
}
left--;
right + + ;
\t\t\t
}
//finally truncate directly
//This truncation is to wrap the header but not the tail
//The left position is already an unequal position
return s.substring(left + 1,right);
}
public static void main(String[] args) {
String res = longestPolindrom("abcdzdcab");
System.out.println(res);
}
}
operation result:
The following is the c++ code implementation
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
//Write a function to return the length of the palindrome string
int expand_around_center(const string & amp; s,int left,int right)
{
int len = s.length();
while (left >= 0 & amp; & amp; right < len & amp; & amp; s[left] == s[right]) {
left--;//Expand to the left
right + + ;//Expand to the right
}
//Once the above is not satisfied, return this length
return right - left -1;
}
//Main function: Find the longest palindrome substring
string longest_palindrome(const string & s)
{
int start = 0, end = 0;//Initialize the starting position and ending position of the longest palindrome substring
int len = s.length();
for (int i = 0; i < len; i + + ) {
//Start the rotation, which is divided into odd number rotation and even number rotation.
int len1 = expand_around_center(s,i,i);
int len2 = expand_around_center(s,i,i + 1);
//The above will all return the length of the text substring, and it may also return 0. We just take the largest one.
int max_len = max(len1,len2); //Depends on header file <algorithm>
//If the currently returned length > the length of the previous record
//Need to update the starting position and ending position
//Memorize this code directly
if (max_len > end - start) {
start = i - (max_len - 1) / 2;
end = i + max_len / 2;
}
}
//After the above overall loop is completed, start and end are both boundaries, and then use substr to intercept
return s.substr(start,end - start + 1);//Why add 1, because end -start will be one less number 2 4 =》 4 - 2 + 1
}
int main()
{
string input = "abcdzdcab";
string result = longest_palindrome(input);
printf("input : %s\
",input.c_str());
//This is the C++ method, which can be understood as string->char*, and then let printf print
printf("Longest palindrom: %s\
",result.c_str());
return 0;
}
operation result:
The following is a diagrammatic analysis of the C++ part
Analysis 1: right – left – 1
Analysis 2:
There are a few small knowledge points that I have to talk about:
The first one: Regarding -1/2=0, it should be -0.5, but 1 and 2 are both integers, and then 0 is truncated later and does not occupy the sign bit. If it is still -4/2 = -2, this There must be a sign bit
Second: printf() cannot print the C language type string of char*, so the string can call the c_str() function to become a string containing a C language pointer.
So if we use C language to process it, just modify the above code and look at the code below.
#include <cstdio>
#include <cstdlib>
#include <cstring>
//Auxiliary function: Find the longest palindrome substring centered on left and right
int expandAroundCenter(char *s, int left, int right) {
int len = strlen(s);
while (left >= 0 & amp; & amp; right < len & amp; & amp; s[left] == s[right]) {
left--;
right + + ;
}
return right - left - 1;//The length of the palindrome string is returned here
}
//Main function: Find the longest palindrome substring
char *longestPalindrome(char *s) {
int start = 0; // The starting position of the longest palindrome substring
int end = 0; // The end position of the longest palindrome substring
int len = strlen(s);
for (int i = 0; i < len; i + + ) {
// Taking each character as the center, expand the palindrome substring in two cases: odd number and even length.
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
// Take the longer of the two situations
int maxLen = len1 > len2 ? len1 : len2;
// If the length of the current palindrome substring is greater than the length of the longest previously recorded palindrome substring
// Then update the starting and ending positions
if (maxLen > end - start) {
start = i - (maxLen - 1) / 2;
end = i + maxLen / 2;
}
}
//Intercept the longest palindrome substring based on the starting and ending positions
char *result = (char*)malloc(sizeof(char) * (end - start + 2));
strncpy(result, s + start, end - start + 1);
result[end - start + 1] = '\0';
return result;
}
int main() {
char input[] = "babad";
char *result = longestPalindrome(input);
printf("Input: %s\
", input);
printf("Longest Palindrome: %s\
", result);
free(result); // Release allocated memory
return 0;
}
The following is an explanation of part of the core code
The time complexity of this algorithm is O(n^2)
Let’s talk about this first