题解：B4101 [CSP-X2023 山东] 回文字符串

yyycj · 2024-12-29 18:27:12 · 题解

题目简述

如果能把一个字符串 S 分割成 n（n>1）个非空子串 S_{1},S_{2},\cdots,S_{n}，并且对于每个 i \in [1,n]，S_{i} = S_{n-i+1} 或者 S_{i} 与 S_{n-i+1} 互为回文，字符串 S 就称为回文字符串。

给定字符串 S，要求判断 S 是否是一个回文字符串。如果是，输出 YES，并输出 n 的最大值；否则输出 NO。

主要思路

如果两个字符串要满足相等或互为回文，那么长度一定相等；并且 S_{i} 和 S_{n-i+1} 刚好可以看做序列 S 的从左往右数第 i 个和从右往左数第 n 个。

所以可以遍历 1 \sim \lceil \frac{|S|}{2} \rceil，记录字符串 s1 和 s2，每次在 s1 前面添加 S[i]，在 s2 前面添加 S[n-i+1]。每次判断一下 s1 和 s2 是否满足条件，由于要求 n 最大，所以如果满足，则立即清空 s1 和 s2，并将答案增加 2。
但是存在一种情况，在 i = \lceil \frac{|S|}{2} \rceil 并且 n 是奇数时，如果满足条件，则 s1 和 s2 表示的是同一个位置的字符，这时候答案就不能增加 2 而是 1。
最后遍历完后，还可能会出现样例#3的情况，n 为偶数导致不会被检测到，所以需要额外特判。

AC Code

#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define endl '\n'
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef unsigned long long ull;
// ----------------------------

// ----------------------------

// ----------------------------
inline int read() {
    int f=1,sum=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
    return sum*f;
}

void print(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9){print(x/10);}
    putchar(char(x%10+'0'));
}

bool check(string s1,string s2) {
    if (s1 == s2) return true;
    reverse(s2.begin(),s2.end());
    return s1 == s2;
}

int main() {
    string s;
    cin>>s;
    // ------------------------
    int ans = 0;
    string s1 = "";
    string s2 = "";
    int n = s.length();
    for (int i=0;i<(n+1)/2;i++) {
        s1 += s[i];
        s2 = s[n-i-1] + s2;
        if (check(s1,s2)) {
            s1 = "";
            s2 = "";
            ans += 2;
            if (n&1 && i==n/2) ans--;
        }
    }
    if (ans && s1!="" && s2!="") ans++;
    // ------------------------
    if (!ans) cout<<"NO";
    else {
        cout<<"YES"<<endl;
        print(ans);
    }
    return 0;
}