题解 | #密码截取#

可以用DP来做，其实就是求最长回文子串。

use std::io::{self, *};

pub fn longest_palindrome(s: String) -> String {
    let arr: Vec<char> = s.chars().collect();
    let mut dp: Vec<Vec<bool>> = Vec::new();
    let mut start_idx = 0usize;
    let mut max = 1usize;
    let count = s.chars().count();
    dp = (0..count).map(|_x| vec![false; count]).collect();
    for size in 2..=count {
        for i in 0..count {
            let j = size + i - 1;
            if j >= count {
                break;
            }
            if arr[i] == arr[j] {
                if size >= 4 {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = true;
                }
            } else {
                dp[i][j] = false;
            }
            if dp[i][j] && size > max {
                max = size;
                start_idx = i;
            }
        }
    }
    arr.iter()
        .enumerate()
        .filter(|&(i, _v)| i >= start_idx && i < start_idx + max)
        .map(|(_i, v)| v)
        .collect()
}

fn main() {
    let stdin = io::stdin();
    for line in stdin.lock().lines() {
        let ll = line.unwrap();
        println!("{}", longest_palindrome(ll).len());
    }
}