C++14(g++5.4) 解法, 执行用时: 33ms, 内存消耗: 8028K, 提交时间: 2020-08-29 10:29:46

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
const ULL base=1e9+7;
int n,dp[N],pre[N];char str[N];
ULL phs[N],shs[N],pw[N];
vector<pii>v;
bool check(int l,int r){
    return phs[r]-phs[l-1]*pw[r-l+1]==shs[l]-shs[r+1]*pw[r-l+1];
}
int main(){
    scanf("%s",str+1);n=strlen(str+1);
    for(int i=1;i<=n;i++)phs[i]=phs[i-1]*base+str[i];
    for(int i=n;i;i--)shs[i]=shs[i+1]*base+str[i];
    pw[0]=1;for(int i=1;i<=n;i++)pw[i]=pw[i-1]*base;
    memset(dp,-0x3f,sizeof(dp));dp[0]=0;
    for(int i=1;i<=n;i++)for(int j=i;j>=1;j--)if(dp[j-1]>=0&&!check(j,i)){
        if(dp[i]<dp[j-1]+1){dp[i]=dp[j-1]+1;pre[i]=j-1;break;}
    }
    if(dp[n]<0){puts("-1");return 0;}
    int now=n;
    while(now)v.pb(pii(pre[now]+1,now)),now=pre[now];
    reverse(v.begin(),v.end());
    printf("%d\n",(int)v.size());
    for(auto x:v){
        for(int i=x.first;i<=x.second;i++)printf("%c",str[i]);puts("");
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 17ms, 内存消耗: 8696K, 提交时间: 2020-08-29 13:12:12

#include<bits/stdc++.h>
using namespace std;

struct node1
{
	int x,id;
}T[200005];
struct node2
{
	int l,r;
}Q[200005];
bool cmp(node2 a,node2 b)
{
	return a.l<b.l;
}
int pre[200005];
unsigned long long H1[200005]={0},H2[200005]={0},P[200005],base=1e9+7;
char R[200005],ans[200005];
int main()
{
    int i,j,k,n,l,r,L=1,DP;
    scanf("%s",R+1),n=strlen(R+1);
    for(P[0]=i=1;i<=n;i++)
    {
        P[i]=P[i-1]*base;
        H1[i]=H1[i-1]*base+R[i];
        H2[i]=H2[i-1]*base+R[n-i+1]; 
    }
    T[0].x=T[0].id=0;
    for(i=1;i<=n;i++)
    {
    	for(j=L-1;j>=0;j--)
    	{
    		l=T[j].id+1,r=i;
    		if(H1[r]-H1[l-1]*P[r-l+1]!=H2[n-l+1]-H2[n-r]*P[r-l+1])break;
		}
    	if(j>=0)pre[i]=T[j].id,T[L].id=i,DP=T[L++].x=T[j].x+1;
    	else DP=0;
	}
    if(!DP)printf("-1\n");
    else 
	{
		printf("%d\n",DP),L=0;
		for(i=n;i;i=pre[i])Q[L].l=pre[i]+1,Q[L++].r=i;
		sort(Q,Q+L,cmp);
		for(i=0;i<L;i++)
		{
			for(k=0,j=Q[i].l;j<=Q[i].r;j++)ans[k++]=R[j];
			ans[k]='\0',printf("%s\n",ans);
		}
	}
    return 0;
}