题意：

演队在口试中非常不幸。在42道考题中，他恰好没有准备最后一道题，而刚好被问到的正是那道题。演队坐在教授面前，一句话也说不出来。但教授心情很好，给了演队最后一次通过考试的机会。他让这个可怜的学生说出考试要考的科目。不幸的是，演队想不起这个科目名字，尽管他记得科目里有诸如安全、程序、设备、可能还有信息学……

为了准备复试，演队决定记住这门课的名字。为了更好地记住那根长字符串，他决定把它分解成回文，并分别学习每个回文。当然，分解过程中的回文数必须尽可能少。

Input

输入一行字符串表示为这门课的名字。这是由小写英文字母组成的非空行。这一行的长度最多是4000个字符。

Output

 第一行输出可以分解科目名称的最小的回文字符串数目。在第二行输出回文所有的回文字符串，由空格分隔。如果有几个答案是可能的，输出其中任何一个。

Input

pasoib

Output

6
p a s o i b

Input

zzzqxx

Output

3
zzz q xx

Input

wasitacatisaw

Output

1
wasitacatisaw

题解：

可以对每一个区间[l,r]用哈希赋一个唯一的值，对区间[l,r]正序哈希一个值，逆序哈希一个值。那么如果区间[l,r]是回文串，那么这个区间的正序哈希值应该等于逆序哈希值

dp[i]=min(dp[j-1]+1,dp[i]),dp[i]代表从1-i区间的回文序列数量

这个状态转移方程就是当区间[j,i]是回文串的时候

如果不会哈希，也可以用一个二维数组来记录一下区间[l,r]是不是回文串，判断回文串就用while循环（这种方法见代码2）

代码1：

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include

代码2：（参考：https://blog.csdn.net/zmx354/article/details/20078995）

1 #include
2
3 #include
4
5 #include
6
7 #include
8
9 #include
10
11 #include
12
13 #include
14
15 #include
16
17
18
19 #pragma comment(linker, "/STACK:1024000000");
20
21 #define LL long long int
22
23 #define ULL unsigned long long int
24
25 #define _LL __int64
26
27 #define INF 0x3f3f3f3f
28
29 #define Mod 1000000009
30
31
32
33 using namespace std;
34
35
36
37 char s[4010];
38
39
40
41 bool dp[4001][4001];
42
43
44
45 int ans[4010];
46
47
48
49 int di[4010];
50
51
52
53 void Output(int l)
54
55 {
56
57 if(l == 0)
58
59 return ;
60
61
62
63 Output(di[l]);
64
65
66
67 if(di[l] != 0)
68
69 printf(" ");
70
71
72
73 for(int i = di[l]+1;i <= l; ++i) 74 75 { 76 77 printf("%c",s[i]); 78 79 } 80 81 } 82 83 84 85 int main() 86 87 { 88 89 int l,i,j,h,e; 90 91 92 93 scanf("%s",s+1); 94 95 96 97 l = strlen(s+1); 98 99 100 101 memset(dp,false,sizeof(dp)); 102 103 104 105 for(i = 1;i <= l; ++i) 106 107 { 108 109 dp[i][i] = true; 110 111 h = i-1; 112 113 e = i+1; 114 115 116 117 while(1 <= h && e <= l && s[h] == s[e]) 118 119 { 120 121 dp[h][e] = true; 122 123 h--,e++; 124 125 } 126 127 128 129 h = i,e = i+1; 130 131 132 133 while(1 <= h && e <= l && s[h] == s[e]) 134 135 { 136 137 dp[h][e] = true; 138 139 h--,e++; 140 141 } 142 143 } 144 145 146 147 memset(ans,INF,sizeof(ans)); 148 149 150 151 ans[0] = 0; 152 153 154 155 di[1] = 0; 156 157 158 159 for(i = 1;i <= l; ++i) 160 161 { 162 163 for(j = i;j >= 1; --j)
164
165 {
166
167 if(dp[j][i])
168
169 {
170
171 if(ans[i] > ans[j-1]+1)
172
173 {
174
175 ans[i] = ans[j-1]+1;
176
177 di[i] = j-1;
178
179 }
180
181 }
182
183 }
184
185 }
186
187
188
189 printf("%d\n",ans[l]);
190
191
192
193 Output(l);
194
195
196
197 puts("");
198
199
200
201 return 0;
202
203 }