Palindromic String manacher
Source
2015 UESTC Training for Search Algorithm and String
My Solution
题意:求出前缀的回文重数的和,(回文重数是递归定义的,详见题面)。
manacher
先用manacher跑出所有的回文子串,并把[i,j]的回文子串半径大小存储在了len[i+j]里,
然后从做到右跑一遍,且同时用f[i]表示0~i的回文子串重数,
每次
if(f[(i+1)/2-1] && len[i] >= i/2+1){
f[i] = f[(i+1)/2-1] + 1;
ans += f[i];
}
else if(len[i] >= i/2+1){
f[i] = 1;
ans += f[i];
}
时间复杂度 O(n)
空间复杂度 O(n)
#include
#include
#include
using namespace std;
typedef long long LL;
const int MAXN = 2e6 + 8;
int len[2*MAXN];
char str[MAXN];
void manacher(int n)
{
int p, q, r;
len[0] = 1;
for(int i = 1, j = 0; i < (n << 1) - 1; i++){ p = i >> 1, q = i - p, r = ((j + 1) >> 1) + len[j] - 1;
len[i] = r < q ? 0 : min(r - q + 1, len[(j << 1) - i]); while(p > len[i] - 1 && q + len[i] < n && str[p - len[i]] == str[q + len[i]]) len[i]++; if(q + len[i] - 1 > r)
j = i;
}
}
int f[MAXN];
int main()
{
#ifdef LOCAL
freopen("e.txt", "r", stdin);
//freopen("e.out", "w", stdout);
int T = 4;
while(T--){
#endif // LOCAL
//ios::sync_with_stdio(false); cin.tie(0);
scanf("%s", str);
int sz = strlen(str), i;
LL ans = 1;
manacher(sz);
f[0] = 1;
for(i = 1; i < sz; i++){
//cout << 0 << " "<< i << " " << len[i] << endl; if(f[(i+1)/2-1] && len[i] >= i/2+1){
f[i] = f[(i+1)/2-1] + 1;
ans += f[i];
}
else if(len[i] >= i/2+1){
f[i] = 1;
ans += f[i];
}
}
printf("%lldn", ans);
#ifdef LOCAL
memset(len, 0, sizeof len);
memset(f, 0, sizeof f);
cout << endl;
}
#endif // LOCAL
return 0;
}
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
https://www.prolightsfxjh.com/
Thank you!
------from ProLightsfx
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
如经许可后转载,请注明出处:https://prolightsfxjh.com/article/uestc-1066-palindromic-string-manacher/
共有 0 条评论