太原做响应式网站,企业网站建设立项请示,网页设计制作与代码整体素材,wordpress安装流程正题
金牌导航 Manacher-4 题目大意
给出一个字符串#xff0c;让你用最少的回文串连接得到该串#xff08;这里连接是可以有重合的#xff09; 解题思路
先用Manacher求出以x为左端点的回文串右端点最大的位置
然后在当前回文串中贪心求下一回文串的右端点 代码
#incl…正题
金牌导航 Manacher-4 题目大意
给出一个字符串让你用最少的回文串连接得到该串这里连接是可以有重合的 解题思路
先用Manacher求出以x为左端点的回文串右端点最大的位置
然后在当前回文串中贪心求下一回文串的右端点 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 50010
using namespace std;
int n, now, ans, last, s[N1], l[N1], r[N1];
string str;
void Manacher()
{int mid 0, mx 0;for (int i 1; i n; i){if (i mx) l[i] min(l[mid * 2 - i], mx - i);else l[i] 1;while(s[i l[i]] s[i - l[i]]) l[i];if (i l[i] mx){mx i l[i];mid i;}r[i - l[i] 1] i l[i] - 1;}
}
int main()
{while(cinstr){memset(r, 0, sizeof(r));n str.size();s[0] s[1] #;for (int i 1; i n; i){s[i * 2] str[i - 1];s[i * 2 1] #;}n n * 2 2;s[n] 0;Manacher();now last r[1] 2;//初始的回文串ans 0;for (int i 2; i n; i){if (i last)last now, ans;//下一个回文串now max(now, r[i] 2);//贪心求最右的点}printf(%d\n, ans);}return 0;
}
