codeforces-873 div1 回文子串-爱代码爱编程
本文借鉴了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