Codeforces 667C Reberland Linguistics 记忆化搜索

链接

Codeforces 667C Reberland Linguistics

题意

思路

代码

#include <iostream>

#include <cstdio>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <map>

#include <set>

#include <cmath>

#include <cstring>

#include <string>

#define LL long long

#define INF 0x3f3f3f3f

#define eps 1e-8

#define MAXN 10005

using namespace std;

string s, ss;

int len;

vector<string> res;

map<string, bool> mp;

map<pair<string, int>, bool> vis;

int f[MAXN];

void dfs(int pos, string last){

	if (vis[make_pair(last, pos)] == true) return;

	int cur = -1;

	if (pos >= len) return;

	for (int i = 0; i < 2; ++i){

		if (pos + 2  + i<= len){

			string temp = s.substr(pos, 2 + i);

			if (!mp[temp]){

				res.push_back(temp);

				mp[temp] = true;

			}

			if (temp != last){

				dfs(pos + 2 + i, temp);

			}

		}

	}

	vis[make_pair(last,pos)] = true;

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("in.txt", "r", stdin);

	//freopen("out.txt", "w", stdout);

#endif // ONLINE_JUDGE

	cin >> ss;

	ss = ss.substr(5);

	len = ss.length();

	for (int i = len - 1; i >= 0; --i){

		s.push_back(ss[i]);

	}

	dfs(0, "");

	int ans = res.size();

	printf("%d\n", ans);

	for (int i = 0; i < res.size(); ++i){

		int len = res[i].length();

		for (int j = 0; j < (len >> 1); ++j){

			swap(res[i][j], res[i][len - j - 1]);

		}

	}

	sort(res.begin(), res.end());

	for (int i = 0; i < res.size(); ++i){

		cout << res[i] << endl;

	}

}