题目链接：
题目大意：
给一个单词，分为前缀和后缀两部分，前缀长度不得小于5，后缀长度只能2或3，请输出后缀的个数和所有的后缀，要求所有后缀均不重复。
分析：
其实这道题没有太多的需要人类智慧的算法（我也不会），直接上DP基本都能过。一开始想当然的穷举，结果喜闻乐见的瞬间爆炸了…
DP之前注意要加一个vis数组记录开始位置和长度，防止重复计算属于前缀里的词。代码中用set存储答案纯属个人喜好，也可以用数组之类的代替，应该没太大区别…（我没试过，错了后果自负）。复杂度也不太会算，提交返回46ms似乎挺快，如有大神会算复杂度，欢迎在下面评论。（对，这个博主就是啥都不会还出来浪…）
代码：（渣渣代码，如有雷同，那就雷同呗）
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<string> 5 #include<cstring> 6 #include<cmath> 7 #include<vector> 8 #include<map> 9 #include<stack> 10 #include<set> 11 #include<cstdlib> 12 #include<deque> 13 #include<queue> 14 #include<bitset> 15 #include<functional> 16 #include<utility> 17 #include<list> 18 #include<iomanip> 19 #include<ctime> 20 #include<cassert> 21 using namespace std; 22 23 char str[10024]; 24 bool vis[10024][4]; 25 set<string> ans; 26 set<string>::iterator it; 27 28 int main() 29 { 30 int len,sum=0; 31 scanf("%s",str); 32 len=strlen(str); 33 memset(vis,true,sizeof(vis)); 34 vis[len][0]=false; 35 for(int i=len;i>=5;i--) 36 { 37 for(int j=0;j<4;j++) 38 { 39 40 if(!vis[i][j]) 41 { 42 string x="",y=""; 43 for(int k=0;k<j;k++) 44 y=y+str[i+k]; 45 for(int k=1;(i-k)>=5&&k<4;k++) 46 { 47 x=str[i-k]+x; 48 if(x!=y&&k>1) 49 { 50 ans.insert(x); 51 vis[i-k][k]=false; 52 } 53 } 54 } 55 } 56 } 57 printf("%d\n",int(ans.size())); 58 for(it=ans.begin();it!=ans.end();it++) 59 { 60 cout<<*it<<endl; 61 } 62 return 0; 63 }
666A-Reberland Linguistics（动态规划）
原文：http://www.cnblogs.com/starryhu/p/5453225.html