給你一個字符串，問你最少通過幾次拼接可以拼成這個串，每次拼接只能拼接兩個回文串，可以重疊。
思路：先求出以每個點為對稱軸的所有的最長回文子串代表的區間，本來要考慮是回文串是奇數還是偶數的，不過 Mancher算法很好的解決了這個問題。。。。
接下來就是選取最少的區間覆蓋整個區間，然後就是赤裸裸的區間覆蓋問題了，用個貪心就可以了：維護一個當前覆蓋到的最遠的距離now_end，那麼接下來要選的線段應該是左端點在now_end的左邊，右端點在now_end的右邊，且盡可能遠的向右延伸。。。。
Mancher 學習：
p[i]表示以i為中心的回文半徑，
p[i]-1剛好是原字符串以第i個為中心的回文串長度。
畫畫圖就知道了，因為兩端配匹的肯定是字符g
Mancher主算法。
學習地址：http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
功能：求出以i為中心的回文半徑p[i];
參數：傳入構造好的字符串長度
特殊說明：因為前面加了一個無效字符，所以下標從1開始。
本題代碼：
[cpp]
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn= 100010;
namespace M {
int n;
struct node {
int a,b;
node() {}
node(int _a,int _b):a(_a),b(_b){};
bool operator < (const node&cmp) const {
return a < cmp.a;
}
}in[50010];
void solve()
{
int ter = 0;
for(int i = 0; i < n; i++) ter = max(ter,in[i].b);
sort(in,in+n);
int ans = 0, pt = 0 , now_end = in[0].a;
while(true)
{
if(now_end > ter) break;
int mx = -1;
while(pt < n)
{
if(in[pt].a <= now_end)
{
if(in[pt].b>mx) mx=in[pt].b;
pt ++;
}
else
{
break;
}
}
now_end = mx + 1;
ans ++;
}
printf("%d\n",ans-1);
}
}
struct Mancher {
char str[maxn];//start from index 1
int p[maxn];
char s[maxn];
int n;
void checkmax(int &ans,int b){
if(b>ans) ans=b;
}
inline int min(int a,int b){
return a<b?a:b;
}
void kp(){
int i;
int mx = 0;
int id;
for(i=1; i<n; i++){
if( mx > i )
p[i] = min( p[2*id-i], p[id]+id-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++) ;
if( p[i] + i > mx ) {
mx = p[i] + i;
id = i;
}
}
}
void pre()
{
int i,j,k;
n = strlen(s);
str[0] = '$';
str[1] = '#';
for(i=0;i<n;i++)
{
str[i*2 + 2] = s[i];
str[i*2 + 3] = '#';
}
n = n*2 + 2;
str[n] = 0;
}
void solve() // 求出所有的最長回文子串所在的區間
{
int & tot = M::n;
tot = 0;
for(int i = 2; i < n; i++)
{
if(i%2&&p[i]==1) continue;
if(i%2)
{
M::in[tot++] = M::node(i/2-p[i]/2+1,i/2+p[i]/2);
//printf("%d %d\n",i/2-p[i]/2+1,i/2+p[i]/2);
}
else
{
M::in[tot++] = M::node(i/2-(p[i]/2-1),i/2+(p[i]/2-1));
//printf("%d %d\n",i/2-(p[i]/2-1),i/2+(p[i]/2-1));
}
}
}
}task1;
int main()
{
while( scanf("%s", task1.s) !=EOF )
{
task1.pre();
task1.kp();
task1.solve();
M::solve();
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn= 100010;
namespace M {
int n;
struct node {
int a,b;
node() {}
node(int _a,int _b):a(_a),b(_b){};
bool operator < (const node&cmp) const {
return a < cmp.a;
}
}in[50010];
void solve()
{
int ter = 0;
for(int i = 0; i < n; i++) ter = max(ter,in[i].b);
sort(in,in+n);
int ans = 0, pt = 0 , now_end = in[0].a;
while(true)
{
if(now_end > ter) break;
int mx = -1;
while(pt < n)
{
if(in[pt].a <= now_end)
{
if(in[pt].b>mx) mx=in[pt].b;
pt ++;
}
else
{
break;
}
}
now_end = mx + 1;
ans ++;
}
printf("%d\n",ans-1);
}
}
struct Mancher {
char str[maxn];//start from index 1
int p[maxn];
char s[maxn];
int n;
void checkmax(int &ans,int b){
if(b>ans) ans=b;
}
inline int min(int a,int b){
return a<b?a:b;
}
void kp(){
int i;
int mx = 0;
int id;
for(i=1; i<n; i++){
if( mx > i )
p[i] = min( p[2*id-i], p[id]+id-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++) ;
if( p[i] + i > mx ) {
mx = p[i] + i;
id = i;
}
}
}
void pre()
{
int i,j,k;
n = strlen(s);
str[0] = '$';
str[1] = '#';
for(i=0;i<n;i++)
{
str[i*2 + 2] = s[i];
str[i*2 + 3] = '#';
}
n = n*2 + 2;
str[n] = 0;
}
void solve() // 求出所有的最長回文子串所在的區間
{
int & tot = M::n;
tot = 0;
for(int i = 2; i < n; i++)
{
if(i%2&&p[i]==1) continue;
if(i%2)
{
M::in[tot++] = M::node(i/2-p[i]/2+1,i/2+p[i]/2);
//printf("%d %d\n",i/2-p[i]/2+1,i/2+p[i]/2);
}
else
{
M::in[tot++] = M::node(i/2-(p[i]/2-1),i/2+(p[i]/2-1));
//printf("%d %d\n",i/2-(p[i]/2-1),i/2+(p[i]/2-1));
}
}
}
}task1;
int main()
{
while( scanf("%s", task1.s) !=EOF )
{
task1.pre();
task1.kp();
task1.solve();
M::solve();
}
return 0;
}
