【bzoj2565】最长双回文串 Manacher+树状数组
数组 最长 回文 树状 Manacher
2023-09-11 14:22:40 时间
原文地址:http://www.cnblogs.com/GXZlegend/p/6802558.html
题目描述
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。
输入
一行由小写英文字母组成的字符串S。
输出
一行一个整数,表示最长双回文子串的长度。
样例输入
baacaabbacabb
样例输出
12
题解
个人并不是擅长单调数据结构,于是用了Manacher后写了树状数组,稍微慢了点。
先求出以每个字符为中心的最大回文半径。
然后想办法求以某个字符结尾的最大回文半径,显然s[i]=i-min{j}+1,其中j≤i且j+p[j]-1≥i。
可以用树状数组维护j+p[j]-1≥i的最小的j,其中需要反过来减一下,因为树状数组是向下查询。
这样求出以某个字符结尾的最大回文半径,并得到最大回文长度。
之后同理求出以某个字符开头的最大回文长度。
最后一个向后一个向前加起来求一下就好了。
时间复杂度O(nlogn),存在更优秀的O(n)算法,参考CQzhangyu's blog。
#include <cstdio> #include <cstring> #include <algorithm> #define N 2000010 using namespace std; int p[N] , f[N] , s1[N] , s2[N] , n; char str[N] , tmp[N]; void update1(int x , int a) { int i; for(i = x ; i <= n ; i += i & -i) f[i] = min(f[i] , a); } void update2(int x , int a) { int i; for(i = x ; i <= n ; i += i & -i) f[i] = max(f[i] , a); } int query1(int x) { int i , ans = 0x7f7f7f7f; for(i = x ; i ; i -= i & -i) ans = min(ans , f[i]); return ans; } int query2(int x) { int i , ans = 0; for(i = x ; i ; i -= i & -i) ans = max(ans , f[i]); return ans; } int main() { int i , mx = 0 , last = 0 , ans = 0; scanf("%s" , str + 1) , n = strlen(str + 1); tmp[0] = '0'; for(i = 1 ; i <= n ; i ++ ) tmp[i * 2 - 1] = '#' , tmp[i * 2] = str[i]; n = n * 2 + 1 , tmp[n] = '#'; for(i = 1 ; i <= n ; i ++ ) { if(mx >= i) p[i] = min(p[last * 2 - i] , mx - i + 1); else p[i] = 1; while(tmp[i - p[i]] == tmp[i + p[i]]) p[i] ++ ; if(mx < i + p[i] - 1) mx = i + p[i] - 1 , last = i; } memset(f , 0x7f , sizeof(f)); for(i = 1 ; i <= n ; i ++ ) update1(n - (i + p[i] - 1) + 1 , i) , s1[i] = 2 * i - 2 * query1(n - i + 1) + 1; memset(f , 0 , sizeof(f)); for(i = n ; i >= 1 ; i -- ) update2(i - p[i] + 1 , i) , s2[i] = 2 * query2(i) - 2 * i + 1; for(i = 2 ; i <= n ; i ++ ) ans = max(ans , (s1[i - 1] + s2[i]) / 2); printf("%d\n" , ans); return 0; }
相关文章
- 算法 - 求一个数组的最长递减子序列(C++)
- HDU 5389 Zero Escape(DP + 滚动数组)
- php数组指定位置、键插入元素
- PHP数组为空的数据显示最上面
- Golang 切片数组打印元素两数只和等于8的下标、无重复字符的最长子串
- 【BZOJ1901】Zju2112 Dynamic Rankings 主席树+树状数组
- PHP 流程控制(while,for,foreach,数组的遍历解构和快速解构)
- [算法]最大连续子数组和,最长重复子串,最长无重复字符子串
- 《Python数据分析》一第2章 NumPy数组2.1 NumPy数组对象
- C语言:数组(2)
- 递归,--遍历多维数组
- [模板题][双指针]数组元素的目标和
- List和数组的互转
- 最长无重复数组
- C# 往string [] arr 数组插入元素
- 63、【数组】AcWing 799. 最长连续不重复子序列——滑动窗口与Hash(C++版本)
- javascript基础,数组(5)
- JS添加、更新和删除 JSON 数组
- 整型数组处理算法(十二)请实现一个函数:最长顺子。[风林火山]
- Java数据结构和算法的数组
- [LeetCode] 845. Longest Mountain in Array 数组中最长的山
- [LeetCode] 718. Maximum Length of Repeated Subarray 最长的重复子数组