|
题目链接 CodeForces - 666A
题目大意
首先定义了一下后缀单词的规则：在一个单词中，由词根和后缀单词组成，词根的长度要大于4，后缀单词的长度为2或者3，并且相邻的两个后缀单词不能相同。给定你一个单词，让你找出你所有的后缀单词。 其实这样看题意还是有一些不清晰，按照我自己的理解就是，看有多少种合法的分法，把所有合法的分法中的后缀单词看成一个集合（这个集合里的后缀单词不重复），输出这个集合中的后缀单词
解题思路
我的天… … …in a row 是连续的意思？？？twice in a row 是连续两次？？？读题读到爆炸… … … …比赛的时候也没有做出来… … … …模拟的要崩溃了 网上说这个题用了dp的思想，可能是我还没悟出dp的真谛吧… … … 我感觉这个题的思想就是个模拟… … … 首先我们定义一个flag[]数组，flag[i]的意思是，从下标为i开始（包括a[i]这个字母）后面的字母可以拆为合法的后缀单词 那么我们考虑一个位置i，我们想知道从这个位置分，可不可以把后面的字母分为合法的后缀单词，我们从后往前遍历：有两种情况，我们先假设从i开始分一个后缀长度为2的后缀单词。 1）这个长度为2的后缀后面还有一个长度2的后缀，因为连续两个后缀是不能相同的，所以我们判断一下这两个后缀单词是不是一样的，并且flag[i+2]要为1，也就是从位置i+2往后的后缀是有一种合法的分法的 2）这个长度为2的后缀后面有一个长度为3的后缀，那么我们就不必比较这两个后缀是不是相同的了，因为长度不同，但是我们要确定flag[i+5]的值为1，也就是说，在这两个后缀后面，从i+5这个位置开始后面的后缀是有一种合法的分法的。 如果我们要从位置i开始分一个后缀长度为3的和长度为2的分析是一样的。 我们用set容器来保存后缀，最后输出就好啦（- -撒花- -）
#include
#include
#include
#include
#include
using namespace std;
int flag[500005];
int main()
{string a,ans;sets;cin>>a;int len=a.length();flag[len]=1;for(int i=len-1; i>4; i--){for(int l=2; lans=a.substr(i,l);if(a.find(ans,i+l)!=i+l||flag[i+5])//判断分法是否合法{s.insert(ans);flag[i]=1;}}}}printf("%d\n",s.size());for(set::iterator its = s.begin(); its != s.end(); ++its)//set输出{cout |