# Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

# Example

Example 1:
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"

# Solution

``````use std::cmp;

impl Solution {
pub fn longest_palindrome(s: String) -> String {
let seq: Vec<char> = s.chars().collect();
let mut len = seq.len();
if len <= 1 {
return s;
}

let mut s_new: [char; 2004] = ['\0'; 2004];
let mut p: [usize; 2004] = [0; 2004];
s_new[0] = '\$';
s_new[1] = '#';
let mut j = 2;

for i in 0..len {
s_new[j] = seq[i];
j += 1;

s_new[j] = '#';
j += 1;
}
s_new[j] = '\0';
len = j;

//start
let mut index: usize = 0;
let mut max_len:usize = 0;

let mut center: usize = 0;
let mut max_right: usize = 0;

for i in 1..len {
if i < max_right {
p[i] = cmp::min(p[2*center-i], max_right-i);
} else {
p[i] = 1;
}

while s_new[i-p[i]] == s_new[i+p[i]] {
p[i] += 1;
}

if max_right < (p[i] + i) {
center = i;
max_right = p[i] + i;
}

if (max_len < p[i])
{
max_len = p[i] -1;
index = (2*i-max_right)/2 ;
}
}

let end: usize = index + max_len;
s[index..end].to_owned()
}
}``````

# 思路说明

https://bestsort.cn/2019/04/28/424/

(=￣ω￣=)··· 暂无内容！

116

17

129

36