前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >CodeForces 666A Reberland Linguistics(DP)

CodeForces 666A Reberland Linguistics(DP)

作者头像
ShenduCC
发布2018-04-26 17:13:31
8250
发布2018-04-26 17:13:31
举报
文章被收录于专栏:算法修养

A. Reberland Linguistics

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

First-rate specialists graduate from Berland State Institute of Peace and Friendship. You are one of the most talented students in this university. The education is not easy because you need to have fundamental knowledge in different areas, which sometimes are not related to each other.

For example, you should know linguistics very well. You learn a structure of Reberland language as foreign language. In this language words are constructed according to the following rules. First you need to choose the "root" of the word — some string which has more than 4 letters. Then several strings with the length 2 or 3 symbols are appended to this word. The only restriction — it is not allowed to append the same string twice in a row. All these strings are considered to be suffixes of the word (this time we use word "suffix" to describe a morpheme but not the few last characters of the string as you may used to).

Here is one exercise that you have found in your task list. You are given the word s. Find all distinct strings with the length 2 or 3, which can be suffixes of this word according to the word constructing rules in Reberland language.

Two strings are considered distinct if they have different length or there is a position in which corresponding characters do not match.

Let's look at the example: the word abacabaca is given. This word can be obtained in the following ways: 

, where the root of the word is overlined, and suffixes are marked by "corners". Thus, the set of possible suffixes for this word is {aca, ba, ca}.

Input

The only line contains a string s (5 ≤ |s| ≤ 104) consisting of lowercase English letters.

Output

On the first line print integer k — a number of distinct possible suffixes. On the next k lines print suffixes.

Print suffixes in lexicographical (alphabetical) order.

Examples

input

代码语言:javascript
复制
abacabaca

output

代码语言:javascript
复制
3
aca
ba
ca

input

代码语言:javascript
复制
abaca

output

0

动态规划,一开始看错了题目,题目的意思是不能有连续相邻的两个后缀是相同的

代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <map>
#include <string>

using namespace std;
#define MAX 10000
struct Node
{
  string a;
}a[MAX*10];
int cmp(Node a,Node b)
{
    return a.a<b.a;
}
int dp[MAX+5];
string s;
map<string,int> m;
int main()
{
    cin>>s;
    int len=s.length();
    memset(dp,0,sizeof(dp));
    dp[len]=1;dp[len-1]=0;dp[len+1]=0;
    m.clear();
    int cnt=0;
    for(int i=len-2;i>=5;i--)
    {
        if(dp[i+2]!=0)
        {
           string  b=s.substr(i,2);
            if(dp[i+2]!=2||b!=s.substr(i+2,2))
            {
                if(!m.count(b))
                {
                     m[b]=1;
                     a[cnt++].a=b;
                }
                dp[i]+=2;
            }
        }
         if(dp[i+3]!=0)
        {
            string b=s.substr(i,3);
            if(dp[i+3]!=3||b!=s.substr(i+3,3))
            {
                if(!m.count(b))
                {
                     m[b]=1;
                     a[cnt++].a=b;
                }
                dp[i]+=3;
            }
        }
    }
    sort(a,a+cnt,cmp);
    printf("%d\n",cnt);
    for(int i=0;i<cnt;i++)
        cout<<a[i].a<<endl;
    return 0;

}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-05-02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档