Skip to content

Instantly share code, notes, and snippets.

@yurahuna
Created October 26, 2016 15:02
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save yurahuna/5bae1edfd3fb8c595a0829e26560ea3a to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
#define int long long // <-----!!!!!!!!!!!!!!!!!!!
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int MAX = 1 << 20;
bool ok[MAX];
string s;
int n;
void dfs(int i, int state, int used) {
if (i == n) {
ok[state] = true;
return;
}
if (s[i] == 'a' || ((used >> (s[i] - 'a')) & 1))
{
dfs(i + 1, state, used | (1 << (s[i] - 'a')));
}
if (s[i] != 'z' && !((used >> (s[i] - 'a' + 1)) & 1))
{
dfs(i + 1, state | (1 << i), used | (1 << (s[i] - 'a' + 1)));
}
}
string f(int state) {
string t;
rep(i, n) {
t += s[i] + ((state >> i) & 1);
}
return t;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
while (cin >> s, s != "#") {
n = s.size();
rep(i, 1 << n) {
ok[i] = false;
}
dfs(0, 0, 0);
int cnt = 0;
vector<int> v;
rep(i, 1 << n) {
if (ok[i]) {
cnt++;
v.emplace_back(i);
}
}
cout << cnt << endl;
vector<string> vs;
rep(i, v.size()) {
vs.emplace_back(f(v[i]));
}
sort(all(vs));
if (cnt <= 10) {
rep(i, vs.size()) {
cout << vs[i] << endl;
}
} else {
rep(i, 5) {
cout << vs[i] << endl;
}
rep2(i, (int)vs.size() - 5, vs.size()) {
cout << vs[i] << endl;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment