字符串连接

题目链接：ybt金牌导航2-1-4

题目大意

给你一个串，你可以通过把任意回文串连接起来（中间重复的重叠多少自己决定）。
问你要构出这个串至少要连接多少次。

思路

首先看到回文串搞一遍Manacher再说。

那我们想，如果你生成了一段在串中 $l\sim r$ 的回文串，那你如果要有前面多少的字符串，就可以和它拼成 $1\sim r$ 的呢？

没错，只要有左边界是 $1$，右边界的是 $l\sim r-1$ 的就可以了。

那我们可以发现它其实可以 DP，设 $f_i$ 为处理好前 $i$ 个字符要多少个回文串，那就枚举右边界的位置，然后选次数最少的。
那怎么优化枚举右边界呢？观察到它其实是求区间最小，直接上线段树。

然后弄一弄就有了，由于输出的是连接次数，那就要输出用的回文串个数减一。

但其实还有 O(n) 的做法。
我们考虑贪心，用Manacher直接求出以每个点为左边界最多可以延伸到哪里。
那我们可以贪心，对于每一段已经确定的回文串，我们在里面继续找，看是否有以它为左边界可以到达更远的地方。然后一旦你走出了前面确定的回文串，那你下一个回文串就是你找到最远的地方用的回文串。
具体可以看看代码。

代码（Manacher + 线段树）

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

char c[50001], s[150001];
int n, nn, dis[150001], l[150001];
int f[150001], tree[600001];

void Manacher() {
	int r = -1, mid = -1;
	
	for (int i = 1; i <= nn; i++) {
		if (i > r) dis[i] = 1;
			else dis[i] = min(dis[2 * mid - i], r - i);
		
		while (i - dis[i] >= 1 && i + dis[i] <= nn && s[i - dis[i]] == s[i + dis[i]])
			dis[i]++;
		
		if (i + dis[i] > r) {
			r = i + dis[i];
			mid = i;
		}
		
		l[i + dis[i] - 1] = max(l[i + dis[i] - 1], dis[i]);
	}
}

void up(int now) {
	tree[now] = min(tree[now << 1], tree[now << 1 | 1]);
}

void clear(int now, int l, int r) {
	if (l == r) {
		tree[now] = 1e9;
		if (l == 0) tree[now] = 0;
		return ;
	}
	
	int mid = (l + r) >> 1;
	clear(now << 1, l, mid);
	clear(now << 1 | 1, mid + 1, r);
	
	up(now);
}

void insert(int now, int l, int r, int pl, int num) {
	if (l == r) {
		tree[now] = min(tree[now], num);
		return ;
	}
	
	int mid = (l + r) >> 1;
	if (pl <= mid) insert(now << 1, l, mid, pl, num);
		else insert(now << 1 | 1, mid + 1, r, pl, num);
	
	up(now);
}

int find(int now, int l, int r, int L, int R) {
	if (L > R) return 0;
	if (l >= L && r <= R) {
		return tree[now];
	}
	
	int mid = (l + r) >> 1, re = 1e9;
	if (mid >= L) re = find(now << 1, l, mid, L, R);
	if (mid < R) re = min(re, find(now << 1 | 1, mid + 1, r, L, R));
	
	return re;
}

void csh() {
	memset(l, 0, sizeof(l));
	memset(f, 0, sizeof(f));
	memset(tree, 0, sizeof(tree));
}

int main() {
	while (scanf("%s", c + 1) != EOF) {
		n = strlen(c + 1);
		
		csh();
		
		nn = (2 * n) + 1;
		for (int i = 1; i <= nn; i++)
			if (i & 1) s[i] = '#';
				else s[i] = c[i >> 1];
		
		Manacher();
		
		for (int i = nn; i >= 1; i -= 2)
			l[i] = max(l[i], l[i + 2] - 2);
		
		clear(1, 0, n + 1);
		for (int i = 3; i <= nn; i += 2) {
			//找到前面可以处理中所需最少的那个
			f[i] = find(1, 0, n + 1, ((i - l[i] - l[i] + 2 + 1) >> 1) - 1, (i - 2 + 1) >> 1) + 1;
			insert(1, 0, n + 1, (i - 2 + 1) >> 1, f[i]);//插入
		}
		
		printf("%d\n", f[nn] - 1);//算的是用的回文串的个数，那拼接次数就是它-1
	}
	
	return 0;
}

代码（Manacher + 贪心）

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

char c[50001], s[150001];
int n, nn, dis[150001], r[150001];
int ans, newp, last;

void Manacher() {
	int R = -1, mid = -1;
	
	for (int i = 1; i <= nn; i++) {
		if (i > R) dis[i] = 1;
			else dis[i] = min(dis[2 * mid - i], R - i);
		
		while (i - dis[i] >= 1 && i + dis[i] <= nn && s[i - dis[i]] == s[i + dis[i]])
			dis[i]++;
		
		if (i + dis[i] > R) {
			R = i + dis[i];
			mid = i;
		}
		
		r[i - dis[i] + 1] = max(r[i - dis[i] + 1], i + dis[i] - 1);
	}
}

void csh() {
	ans = 0;
	memset(r, 0, sizeof(r));
}

int main() {
	while (scanf("%s", c + 1) != EOF) {
		n = strlen(c + 1);
		
		csh();
		
		nn = (2 * n) + 1;
		for (int i = 1; i <= nn; i++)
			if (i & 1) s[i] = '#';
				else s[i] = c[i >> 1];
		
		Manacher();
		
		newp = last = r[1] + 2;
		for (int i = 2; i <= nn; i++) {
			if (i == last) {//要拿新的了
				ans++;
				last = newp;//根据能拿到最远的确定这个到哪里
			}
			newp = max(newp, r[i] + 2);//贪心，在这个限度内能拿到多远就多远
		}
		
		printf("%d\n", ans);
	}
	
	return 0;
}