题目描述
(暴力解法)7/12
类似于计数类DP(算法基础课,整数划分)
周赛因为通过人数少,赛时没有深入思考
首先想到的是枚举所有可能词根的长度,然后将后面的词缀长度划分,
例如把长度为n的字符串划分成长度为2,3的子字符串,并且满足连续字符串不相等的条件
为了方便枚举方案,我们去掉前5个字符,并且将字符串反转,
类似于走楼梯,每次走2层或者3层,不能超过总楼梯数
这里多一个限制条件:相邻的字符串不能相同
DFS
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
set<string> res;
string s;
int n;
void dfs(int u,string last)
{
if(u > n)
{
return;
}
string s1 = s.substr(u,2) , s2 = s.substr(u,3);
//cout << s1 << " " << s2 << endl;
string backup1 = s1 , backup2 = s2;
reverse(backup1.begin(),backup1.end());
reverse(backup2.begin(),backup2.end());
if(s1 != last && u + 2 <= n)
{
res.insert(backup1);
dfs(u + 2,s1);
}
if(s2 != last && u + 3 <= n)
{
res.insert(backup2);
dfs(u + 3,s2);
}
}
int main()
{
cin >> s;
s = s.substr(5);
n = s.length();
reverse(s.begin() , s.end() );
dfs(0,"");
cout << res.size() << endl;
for(auto x : res)
{
cout << x << endl;
}
}
算法二(还不是很理解)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 10010;
int n;
string s;
bool f[N];
//如果f[i]为真,那么他后面跟的第一个词缀是一组答案,并且后面不会出现重复词缀的排列
int main()
{
cin >> s;
n = s.size();
f[n - 1] = true;
set<string> res;
for (int i = n - 2; i >= 4; i -- )//以i结尾做词根的合法长度
for (int j = 2; j <= 3; j ++ )//i后面接的是长度2或者3的词缀
if (f[i + j])//判断i+j能否作为合法的词根,即后面的字串能否成为合法的词缀
{//满足条件,即为i可以作为词根 ,这时候我们需要判断i后面接的长度为2或者3长度的字串是否合法
string a = s.substr(i + 1, j);
string b = s.substr(i + 1 + j, j);
if (a != b || f[i + 5])//如果a跟b不相等,那肯定合法,如果f[i+5]合法,那么两部分长度不同,肯定合法
{
f[i] = true;
res.insert(a);
}
}
cout << res.size() << endl;
for (auto& t: res) cout << t << endl;
return 0;
}