代码编织梦想

本文借鉴了codeforces大佬fantasy的代码采用马拉车算法

//Awwawa! Dis cold yis ratten buy Pikachu!
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 500015, N = maxn + 10;
char s[maxn];
char ch[N<<1];
int f[N<<1];
//f[i*2]: i centered; f[i*2+1]: (i,i+1) centered
void manacher(char *s) {
    int n=strlen(s),id=0,mx=0;
    for (int i = 0; i <= 2 * n + 10; i++)
        f[i] = 0, ch[i] = 0;
    ch[0]='$'; ch[1]='#';
    for(int i=1;i<=n;i++)
        ch[i*2]=s[i-1], ch[i*2+1]='#';
    ch[n*2+2]='#';
    for(int i=0;i<=2*n+10;i++) f[i]=0;
    for(int i=1;i<=2*n+2;i++) {
        if(i>mx) f[i]=1; else f[i]=min(f[id*2-i],mx-i);
        while(ch[i-f[i]]==ch[i+f[i]]) f[i]++;
        if(i+f[i]>mx) {mx=i+f[i]; id=i;}
    }
}
int main() {
    int t;
    cin >> t;       //0 1 2 3 2 1 6 1 2 5 2 1 2 1 1 4
    while (t--) {  // 0 1 2 3 2 1 6 1 2 5 2 1 2 1 1 0 4
        int n;
        scanf("%d", &n);
        scanf("%s", s);
        manacher(s);
        ///先弄一个马拉车
        vector<vi > ot(n, vi());  ///二维数组
        vi dp(n + 1, 0);      ///一维dp数组
        dp[n] = 0;
        set<int> tot;
        ll sum = 0;
        for (int i = n - 1; i >= 0; i--) {                        ///     0 1 2 3 4 5
            int cur = f[i + (i + 3)] / 2;       ///获取回文长度                       a a b a a b
            ///         $#a#a#b#a#a#b##      ch
            ///  012345678910111213
            ///  0 1 2 3 2 1 6 1 2 5 2 1 2 1 1       4

            if (cur >= 1) {
                tot.insert(2 * i + 1);    ///左边界放入set
                int e = i - cur;             /// 下一个位置
                if (e >= 0) ot[e].pb(2 * i + 1);    ///左边界放到二维数组里面
            }
            for (auto v: ot[i]) {   ///访问二维数组
                tot.erase(v);             ///将其中元素从set里去除
                // cout << v << endl;
            }
            if (!tot.size()) dp[i] = 0;     ///set 为空则dp表为0
            else {
                // cout << "f" << *(tot.begin()) << endl;
                dp[i] = 1 + dp[(*tot.begin()) + 1 - i];       ///        dp[3]=1+dp[5]
            }
            sum += dp[i];
        }
        cout << sum << '\n';
    }
    return 0;
}

i=5时,cur=0,二维数组空没删元素,dp=0
i=4时,cur=0,二维数组空没删元素,dp=0
i=3时,cur =2,set插入左边界7,e(next)=1,二维1中放入snew左边界7,二维3为空
Set不用删除,dp[3]=1+dp[5]
i=2 Cur=0 dp[2]=1+dp[6]=1
I=1 Cur=0 把set中的7去掉 dp[1]=0
I=0 Cur=1
插入左边界1 e=-1 二维数组中不用插入 dp[0]=1+dp[2]=2

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/luoxutimberjack/article/details/130784169