神奇项链

wjh15101051's space

卧薪尝胆，厚积薄发。

神奇项链

Date: Wed Sep 26 20:13:31 CST 2018

In Category: NoCategory

Description：

求最少把几个回文串拼起来可重叠可以覆盖整个字符串。

$1\leqslant n \leqslant 50000$

Solution：

先用 $\text{manacher}$ 求出每个位置的最长回文半径，然后问题就变成了用尽量少的线段覆盖整个线段，可以把所有线段按左端点排序，然后贪心的每次找左端点在当前右端点之前的右端点最靠右的区间选择它即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 50010

char c[MAXL],s[MAXL << 1];

int tot;

int h[MAXL << 1];

struct line

{

	int l,r;

}e[MAXL << 1];

int cnt = 0;

bool cmp_l(line a,line b){return a.l < b.l;}

int main()

{

	while(scanf("%s",c + 1) != EOF)

	{

		int n = strlen(c + 1);tot = 0;s[++tot] = '#';

		for(int i = 1;i <= n;++i)

		{

			s[++tot] = c[i];s[++tot] = '#';

		}

		n = tot;

		int maxr = 1,pos = 1;

		cnt = 0;

		for(int i = 1;i <= n;++i)

		{

			if(maxr > i)h[i] = min(h[2 * pos - i],maxr - i + 1);

			else h[i] = 1;

			while(i - h[i] >= 1 && i + h[i] <= n && s[i - h[i]] == s[i + h[i]])++h[i];

			if(i + h[i] - 1 > maxr)

			{

				pos = i;

				maxr = i + h[i] - 1;

			}

			if((i - h[i] + 1 + 1) / 2 <= (i + h[i] - 1) / 2)

			{

				++cnt;e[cnt].l = (i - h[i] + 1 + 1) / 2;e[cnt].r = (i + h[i] - 1) / 2;

			}

		}

		n = n / 2;

		sort(e + 1,e + 1 + cnt,cmp_l);

		int cur = 0;

		int ans = 0;

		for(int i = 1;i <= cnt;)

		{

			int r = 0;

			for(;i <= cnt && cur >= e[i].l - 1;++i)r = max(r,e[i].r);

			cur = r;

			++ans;

			if(cur == n)break;

		}

		cout << ans - 1 << endl;

	}

	return 0;

}

In tag: 字符串-manacher 算法-贪心

wjh15101051