算法1:递推
C++ 代码
#include<iostream>
#include<set>
using namespace std;
typedef long long ll;
#define int long long
#define endl '\n'
const int N = 10010;
int n;
string s;
//f[i]:字符串s[0~i]能否作为词根
bool f[N];
void solve()
{
cin >> s;
n = s.size();
f[n - 1] = true;
set<string> res;
for (int i = n - 3; i >= 4; i--)
for (int j = 2; j <= 3; j++)
if (f[i + j])
{
string a = s.substr(i + 1, j);
string b = s.substr(i + 1 + j, j);
if (a != b || f[i + 5])
{
// s[i+1...]能分出后缀,故f[i]可以作为词根
f[i] = true;
res.insert(a);
}
}
cout << res.size() << endl;
for (auto& t : res) cout << t << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
算法2:记忆化搜索
C++ 代码
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
#define int long long
#define endl '\n'
string str;
set<string>sset;
bool st[10005];
bool judge(int a, int b, int c, int d) {
for (int i = a, j = c; i <= b && j <= d; i++, j++) {
if (str[i] != str[j])return 0;
}
return 1;
}
// 记状态t表示为s[0~t]可以作为一个词根
void dfs(int t) {
if (st[t])return;// 剪枝
st[t] = 1;
// 将当前状态t划分为如下子状态
if (t - 2 >= 4)sset.insert(str.substr(t - 1, 2));
if (t - 3 >= 4)sset.insert(str.substr(t - 2, 3));
if (t - 4 >= 4) {
if (!judge(t - 3, t - 2, t - 1, t)) {
sset.insert(str.substr(t - 3, 2));
dfs(t - 4);
}
}
if (t - 6 >= 4) {
if (!judge(t - 5, t - 3, t - 2, t)) {
sset.insert(str.substr(t - 5, 3));
dfs(t - 6);
}
}
if (t - 5 >= 4) {
sset.insert(str.substr(t - 4, 2));
sset.insert(str.substr(t - 4, 3));
dfs(t - 5);
}
}
void solve() {
cin >> str;
dfs(str.length()-1);
cout << sset.size() << endl;
for (auto t : sset) {
cout << t << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
return 0;
}