题解：B4101 [CSP-X2023 山东] 回文字符串
DL_ZZS_114514 · · 题解
B4101 题目传送门
可以利用双指针的思想
设立指针
- 如果
s[L]=s[R] ，那就说明这两个字符可以满足形成两个回文的子串，此时ans 就增加2。 -
否则，
s[L]\neq s[R] ，此时无法满足条件，那么就从这里开始构造两个字符串sl 和sr ，继续遍历，sl 和sr 分别表示从此时的L 和R 开始，一直到两个字符串互为回文，或者L\geq R （即L ,R 相遇）时的字符串。- 其中如果构造的两个字符串互为回文，则又有了两个满足条件的子串。
ans 增加2。 - 如果直到
L 和R 相遇还无法满足，那么只有这两个串合起来的一个大串。ans 增加1。
- 其中如果构造的两个字符串互为回文，则又有了两个满足条件的子串。
注意一点：
当判断构造的两个子串
参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int ans;
signed main() {
//freopen("palindrome.in","r",stdin);
//freopen("palindrom.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
//如果你用cin，建议关闭同步流增加效率
cin>>s;
int l=0,r=s.size()-1;
while(l<r){
if(s[l]==s[r]){
ans+=2;
l++;r--;//继续遍历
if(l==r) ans++;//如果再遍历一步后，L和R正好重合，那么此时又能创造一个大字符串，所以ans再加一
}
else{
string sl,sr;
while(l<r){
sl+=s[l++];
sr=s[r--]+sr;//给子串拼接新遍历的字符
if(sl==sr) break;//判断是否互为回文
}
if(sl!=sr){
ans++; //不回文，增加一个
}
else ans+=2;//回文，增加两个
}
}
if(ans<=1){
cout<<"NO\n";
}//如果到最后只有一个串满足，那就是大串自己，所以输出 NO
else{
cout<<"YES\n"<<ans<<"\n";
}//否则，大串满足条件，再输出能分割成的子串数 ans
return 0;
//完结撒花
}