# 2023-01-08：小红定义一个仅有r、e、d三种字符的字符串中， 如果仅有一个长度不小于2的回文子串

2023-01-08：小红定义一个仅有r、e、d三种字符的字符串中，

n = 1, 输出0，
n = 2, 输出3，
n = 3, 输出18。

``````use std::iter::repeat;
fn main() {
for i in 1..=10 {
println!("长度为{}, 答案:{},{}", i, num1(i), num2(i));
}
}

// 暴力方法
// 为了观察规律
// 具体方法论，在体系学习班，章节39 : 根据对数器找规律
fn num1(n: i32) -> i32 {
let mut p: Vec<u8> = repeat(0).take(n as usize).collect();
return process1(&mut p, 0);
}

fn process1(p: &mut Vec<u8>, i: i32) -> i32 {
if i == p.len() as i32 {
let mut dp = get_manacher_dp(p);
let mut cnt = 0;
for p in dp.iter() {
if p - 1 > 3 {
return 0;
}
if p - 1 >= 2 {
cnt += 1;
}
if cnt > 1 {
return 0;
}
}
return if cnt == 1 { 1 } else { 0 };
} else {
let mut ans = 0;
p[i as usize] = 'r' as u8;
ans += process1(p, i + 1);
p[i as usize] = 'e' as u8;
ans += process1(p, i + 1);
p[i as usize] = 'd' as u8;
ans += process1(p, i + 1);
return ans;
}
}

fn get_manacher_dp(s: &mut Vec<u8>) -> Vec<i32> {
let mut str = manacher_string(s);
let mut p_arr: Vec<i32> = repeat(0).take(str.len()).collect();
let mut cc = -1;
let mut rr = -1;
for i in 0..str.len() as i32 {
p_arr[i as usize] = if rr > i {
get_min(p_arr[(2 * cc - i) as usize], rr - i)
} else {
1
};
while i + p_arr[i as usize] < str.len() as i32 && i - p_arr[i as usize] > -1 {
if str[(i + p_arr[i as usize]) as usize] == str[(i - p_arr[i as usize]) as usize] {
p_arr[i as usize] += 1;
} else {
break;
}
}
if i + p_arr[i as usize] > rr {
rr = i + p_arr[i as usize];
cc = i;
}
}
return p_arr;
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}

fn manacher_string(s: &mut Vec<u8>) -> Vec<u8> {
let mut res: Vec<u8> = repeat(0).take(s.len() * 2 + 1).collect();
let mut index = 0;
let mut i = 0;
while i != res.len() {
res[i as usize] = if (i & 1) == 0 {
'#' as u8
} else {
index += 1;
s[index - 1]
};
i += 1;
}
return res;
}

// 正式方法
// 观察规律之后，把规律变成代码
fn num2(n: i32) -> i32 {
if n == 1 {
return 0;
}
if n == 2 {
return 3;
}
if n == 3 {
return 18;
}
return 6 * (n + 1);
}
``````

``````// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

contract Hello{
function main() public pure returns (int32[] memory){
int32[] memory ans = new int32[](10);
for (int32 i = 1; i <= 10; i++) {
ans[uint32(i-1)] = num2(i);
}
return ans;
}

// 正式方法
// 观察规律之后，把规律变成代码
function  num2(int32 n) public pure returns(int32) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 3;
}
if (n == 3) {
return 18;
}
return 6 * (n + 1);
}

}``````

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

209

10

19

5