题解：P15696 [2018 KAIST RUN Spring] QueryreuQ

· · 题解

一、题意理解&分析题面

我们通读题面以后可以发现题目要求我们操作一个字符串，每次在末尾加或减一个字符，考虑到题目要求我们求回文串，我们可以联想到一些关于求回文串算法，这时我们就可以想到马拉车算法，其可以帮助我们在 O(Q) 的时间下快速求出目标字符串中有几个回文串。
（为什么是 O(Q)？因为我们可以发现原字符串是空的，是从操作以后才开始添加字符的，因此字符串的长度最多就是 Q）

在此基础上我们观察到数据范围，Q 最大是 10000，因此可以 O(Q^2) 通过本题，我们可以直接简单循环进行预处理，将末尾字符去掉，而添加字符操作则可以直接在原有字符上进行添加，最后输出即可。

简单做法总结：先预处理字符串达到题目输入效果，再使用马拉车模板直接计算回文串个数，最后输出即可。
（不要忘记 manacher 内有些全局变量需要多测清空，而字符串不需要清空因为是在原先基础上操作的！）

难点就在于实现马拉车了然后就差不多了。

二、代码实现

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string s1;
int c=0,ri=0;
string init(string s1)//马拉车中的预处理字符串
{
    string s;
    for(int i=0;i<s1.size();i++)
    {
        s+='#';
        s+=s1[i];
    }
    s+='#';
    return s;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)//习惯使用T，其实就是题目里的Q次操作
    {
        c=0,ri=0;
        char a;
        cin>>a;
        if(a=='-')//这个地方就是按照题目要求添加字符或删减字符
        {
            string nows;
            for(int i=0;i<s1.size()-1;i++)nows+=s1[i];
            s1=nows;
        }
        else s1=s1+a;
        string s=init(s1);//从这里开始就是马拉车模板，详细参见P3805
        int n=s.size()-1;
        vector<int> r(n+1,0);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(i<ri)
            {
                int j=2*c-i;
                r[i]=min(r[j],ri-i);
            }
            else r[i]=0;
            while(i-r[i]>=0&&i+r[i]<=n&&s[i-r[i]]==s[i+r[i]])r[i]++;
            if(i+r[i]>ri)c=i,ri=i+r[i];
            ans+=r[i]/2;//累加每一个回文中心的回文串数量（因为r[i]表示的是最长回文半径，而其包含了上面马拉车预处理的"#"，所以事实上其应当是原字符串的长度。为求出长度小于r[i]且与其同个回文中心的数量，我们应当除以2）
        }
        cout<<ans<<" ";//直接输出即可
    }

    return 0;
}

以上就是全部内容，希望可以帮助到你。