题解：SP34117 JUSTAPAL - Just a Palindrome

DemonPlayer · 2025-01-08 14:45:40 · 题解

先看代码吧。

#include<bits/stdc++.h>
using namespace std;

int IsH(string& s,int left,int right){
    int n=s.size();
    while(left>=0&&right<n&&s[left]==s[right]){
        left--;
        right++;
    }
    return right-left-1;
}


int solvo(string& s){
    int n=s.size();
    int maxLen=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            string st=s;
            swap(st[i],st[j]);
            for(int k=0;k<2*n-1;k++){
                int left=k/2;
                int right=left+(k%2);
                int len=IsH(st, left, right);
                maxLen=max(maxLen, len);
            }
        }
    }
    return maxLen;
}

int T;
string s;

int main(){
    scanf("%d",&T);
    while(T--){
        cin>>s;
        cout<<solvo(s)<<endl;
    }
    return 0;
}

代码解释：

1. IsH 函数：

• 该函数接收一个字符串 s 以及起始的左右指针 left 和 right。
• 函数会不断扩展左右指针，只要 left 指针不越界、right 指针不越界且左右指针指向的字符相等，就继续扩展。
• 扩展方式是将 left 减 1，right 加 1。
• 最终返回扩展后的回文子串的长度，计算方式是 right - left - 1。

2. solvo 函数：

• 首先获取字符串 s 的长度 n，并初始化最大长度 maxLen 为 0。
• 两重 for 循环用于枚举可能的交换位置 i 和 j。
  • 创建一个新字符串 newStr 并复制 s，然后交换 newStr 中 i 和 j 位置的字符。
  • 另一个 for 循环用于枚举可能的中心位置，center 的范围是 0 到 2 \times n - 1。
    • 根据 center 计算 left 和 right 指针，left 是 center \div 2，right 是 left+(center \bmod 2)。
    • 调用 solvo 函数得到当前中心扩展后的回文子串长度 len，并更新 maxLen 为当前最大值。