【题意】给你一个字符串,然后删去前五个字符后剩下的部分能划分出几种单词来,单词的长度只能为2 or 3,注意一种划分方案中不允许出现两个连续相等的单词,很容易想到我们可以按位置枚举这些单词,然后需要用DP判断这个单词能不能被划分出来。
【分析】这里我看了本次比赛第一名的方法,确实有被惊艳到!简直就是set大暴力呀,代码相对于其他也显得很简单!
【AC代码】
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
set<string>v[maxn];//用来判重set
set<string>ans;//存答案的set
int main(){
string s;
cin>>s;
int len = s.length();
for(int i=len-1; i>4; i--){
string t = s.substr(i,1);
for(int j=i-1; j>=i-2&&j>4; j--){
t = s[j]+t;
if (v[i + 1].size() == 1 && !v[i + 1].count(t) || v[i + 1].size() > 1 || i + 1 >= len) {
v[j].insert(t);
ans.insert(t);
}
}
}
cout<<ans.size()<<endl;
for(auto x:ans){
cout<<x<<'\n';
}
return 0;
}