题目链接：http://codeforces.com/contest/666/problem/A
题意：
给一个字符串，然后你你需要切一个长度至少为5的前缀下来，然后剩下的都得切成是长度为2或者3的字符串

你需要连续的切出来的字符串都不一样，问你能够切出多少不同的块

解法：

前面那个直接n-5就好了，就把前缀切下来了

然后考虑dp,dp[i][0]表示第i个位置，切下长度为2的可不可行

dp[i][1]表示第i个位置，切下长度为3的可不可行

转移显然有：
dp[i][0] = dp[i-2][1]|| (s[i]!=s[i-2]||s[i-1]!=s[i-3])&&dp[i-2][0]
dp[i][1] = dp[i-3][0]|| (s[i]!=s[i-3]||s[i-1]!=s[i-4]||s[i-2]!=s[i-5])&&dp[i-3][1]

把所有合法的字符串汽切割放到vector排序去重输出即可。复杂度 O(n)的dp+O(排序去重=nlogn)

//CF 666A

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e4+6;
char str[maxn];
int dp[maxn][2]; ///dp[i][0]表示第i个位置切下长度为2的是否可行,dp[i][1]表示第i个位置切下长度为3的是否可行
///dp[i][0] = dp[i-2][1]|| (s[i]!=s[i-2]||s[i-1]!=s[i-3])&&dp[i-2][0]
///dp[i][1] = dp[i-3][0]|| (s[i]!=s[i-3]||s[i-1]!=s[i-4]||s[i-2]!=s[i-5])&&dp[i-3][1]
int n;
vector <string> ans;

int main(){
 scanf("%s", str);
 n = strlen(str);
 reverse(str, str+n);
 for(int i = 1; i < n-5; i++){
 if(i==1){
 string s1="";
 s1+=str[i];
 s1+=str[i-1];
 ans.push_back(s1);
 dp[i][0] = 1;
 }
 if(i==2){
 string s1="";
 s1+=str[i];
 s1+=str[i-1];
 s1+=str[i-2];
 ans.push_back(s1);
 dp[i][1]=1;
 }
 if(i>=3&&(str[i]!=str[i-2]||str[i-1]!=str[i-3])&&dp[i-2][0]==1){
 string s1="";
 s1+=str[i];
 s1+=str[i-1];
 ans.push_back(s1);
 dp[i][0]=1;
 }
 if(i-2>=0&&dp[i-2][1]==1){
 string s1="";
 s1+=str[i];
 s1+=str[i-1];
 ans.push_back(s1);
 dp[i][0]=1;
 }
 if(i>=5&&(str[i]!=str[i-3]||str[i-1]!=str[i-4]||str[i-2]!=str[i-5])&&dp[i-3][1]){
 string s1="";
 s1+=str[i];
 s1+=str[i-1];
 s1+=str[i-2];
 ans.push_back(s1);
 dp[i][1]=1;
 }
 if(i>=3&&dp[i-3][0]){
 string s1="";
 s1+=str[i];
 s1+=str[i-1];
 s1+=str[i-2];
 ans.push_back(s1);
 dp[i][1]=1;
 }
 }
 sort(ans.begin(), ans.end());
 ans.erase(unique(ans.begin(), ans.end()), ans.end());
 cout << ans.size()<< endl;
 for(int i = 0; i < ans.size(); i++){
 cout << ans[i] << endl;
 }
}