题目链接:http://codeforces.com/problemset/problem/666/A

思路:dp[i][0]表示第a[i-1]~a[i]组成的字符串是否可行,dp[i][1]表示第a[i-2]~a[i]组成的字符串是否可行,显然dp[len-2][0(1)]必定不可行。

转移方程:

dp[i][0] = dp[i+3][1] || dp[i+2][0] && (tmp1 != tmp2);
dp[i][1] = dp[i+2][0] || dp[i+3][1] && (tmp1 != tmp2);
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
typedef long long ll;
char a[N];
string ans[N<<1];
string tmp1 ,tmp2;
bool dp[N][2];
int cur ,num = 1;
int main()
{
scanf("%s",a);
int len = strlen(a);
if(len <= 6)
{
printf("0\n");
return 0;
}
dp[len-1][0] = 1;
tmp1 = "";
tmp1 += a[len-2];
tmp1 += a[len-1];
ans[cur++] = tmp1;
if(len > 7)
{
dp[len-1][1] = 1;
tmp1 = "";
tmp1 += a[len-3];
tmp1 += a[len-2];
tmp1 += a[len-1];
ans[cur++] = tmp1;
}
for(int i = len - 3 ;i >= 6 ;i--)
{
tmp1 = "";
tmp1 += a[i-1];
tmp1 += a[i];
tmp2 = "";
tmp2 += a[i+1];
tmp2 += a[i+2];
dp[i][0] = dp[i+3][1] || dp[i+2][0] && (tmp1 != tmp2);
if(dp[i][0])
ans[cur++] = tmp1; if(i == 6)
continue; tmp1 = "";
tmp1 += a[i-2];
tmp1 += a[i-1];
tmp1 += a[i];
tmp2 = "";
tmp2 += a[i+1];
tmp2 += a[i+2];
tmp2 += a[i+3];
dp[i][1] = dp[i+2][0] || dp[i+3][1] && (tmp1 != tmp2);
if(dp[i][1])
ans[cur++] = tmp1;
}
sort(ans ,ans + cur);//排序
for(int i = 1 ; i < cur ; i++)
{
if(ans[i] != ans[i-1])//并去重
num++;
}
printf("%d\n",num);
cout<<ans[0]<<"\n";
for(int i = 1 ; i < cur ; i++)
{
if(ans[i] != ans[i-1])
cout<<ans[i]<<"\n";
}
return 0;
}

最新文章

  1. PHP的基本排序算法
  2. MySQL-Front 建表引发的一点小思考(数据表格模版)
  3. fstream的使用方法介绍
  4. RecyleView 简析
  5. mysql 索引 详解
  6. ASP.NET MVC中几个运用技巧
  7. Java中的toString()方法
  8. [OJ] Single Number II
  9. POJ 1416 Shredding Company
  10. Fedora 21 安装Infinality
  11. hdu 5533 Dancing Stars on Me(数学,水)
  12. keepalive的 nopreempt 非抢占
  13. windos环境apache+mysql+php+Discuz的安装配置
  14. hbase的HQuorumPeer和QuorumPeerMain
  15. Android 轮播图Banner切换图片的效果
  16. JavaScript的几种克隆(clone)方式【转】
  17. Python Selenium系列学习
  18. linux无法启动httpd服务问题
  19. 手写AVL 树(上)
  20. JSON.NET 空值处理, 数字转字符,时间格式化

热门文章

  1. [CCF] Z字形扫描
  2. jQuery判断元素是否存在方法
  3. (转)使用myeclipse生成实体类和hibernate映射文件
  4. 安装DotNetCore.1.0.0-VS2015Tools.Preview2失败解决方案
  5. ASP.NET MVC view引入命名空间
  6. centos7 docker mysql56
  7. Linux基础※※※※如何使用Git in Linux(二)
  8. Android 签名工具 shell脚本
  9. Windows下面安装easy_install报UnicodeDecodeError: 'ascii' codec can't decode byte解决方法
  10. 常用js,css文件统一加载方法,并在加载之后调用回调函数