【题解】AT_abc468d Pre-Palindrome

· · 题解

题目传送门

欢迎来博客园阅读！

题意简述

定义一个字符串为好字符串，当且仅当：

给定字符串 S，求其所有子串中好字符串的个数。

思路

观察数据范围我们可以知道这道题 \Theta (n^2) 可以过。

观察样例解释：

除了从第 1 个到第 4 个字符的 abab 和从第 2 个到第 5 个字符的 baba 以外的 13 个子串都是好字符串。

这给予我们灵感去从反面思考问题。

我们可以遍历每一个子串。由于需要考虑与回文相关的性质，这里我遍历的方法是固定一个子串的对称轴后两个端点依次向外移动。

考虑什么情况下不是好字符串。我们发现，在端点移动的过程中，如果两个端点对应的字符不同，第一次可以修改，但是第二次遇到这种，从这一个开始后面的就都至少有两处需要修改了。也就是说，对称轴固定后，移动端点是遇到第二个字符不同的位置时，从这一个位置开始向外的部分都对答案不再产生贡献。

然后是一点细节，枚举对称轴时：

  1. 子串的长度有奇偶性的区别。也就是说实际上要枚举的对称轴是 n 个点和 n-1 个空；
  2. 对于长度为奇数的子串，注意只有一个字符也是好字符串。

于是就做完了。

:::success[代码]

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);i<=(int)(b);i++)
using namespace std;
typedef long long ll;

int n;
string s;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>s;
    n=s.size();
    s='#'+s;
    ll ans=0;
    loop(i,1,n){
        bool flag=1;
        loop(j,0,n){
            if(i-j<1||i+j>n)break;
            if(s[i-j]==s[i+j])ans++;
            else {
                if(!flag)break;
                ans++,flag=0;
            }
        }
    }
    loop(i,1,n-1){
        bool flag=1;
        loop(j,0,n){
            if(i-j<1||i+1+j>n)break;
            if(s[i-j]==s[i+1+j])ans++;
            else {
                if(!flag)break;
                ans++,flag=0;
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

:::

完结撒花花！