CF633C(trie树dfs / 字符串hash + 线性dp)

 题意：
描述了一种加密技术，现在将加密后的字符串和字典给出，要你求还原后的字符串。
加密方式：
①将所有字母改为小写字母
②将所单词翻转
③将所有空格去掉

思路:

解法一:(字符串hash+dp)原串长度只有1e4,然后我们可以考虑dp,令f_i为以第i个位置开头的待匹配子串的hash值,然后线性dp即可.不过cf卡unordered_map,会T,

解法二:(trie树)考虑对每个待匹配的子串倒着插入字典树,然后dfs即可.

代码:

思路一:

#include <bits/stdc++.h>
// #define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int base = 131, N = 2e6 + 10;
int n, m;
ull f[N];
unordered_map<ull, string> mp;
string ori, s;
void solve() {
	cin >> n >> ori >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> s;
		ull hsh = 0;
		for (int j = SZ(s) - 1; j >= 0; --j) hsh = hsh * base + tolower(s[j]) - 'a' + 1;
		mp[hsh] = s;
	}
	f[n] = 1;
	for (int i = n - 1; i >= 0; --i) {
		ull hsh = 0;
		for (int j = 1; i + j - 1 <= n; ++j) {
			hsh = hsh * base + ori[i + j - 1] - 'a' + 1;
			if (mp.count(hsh) && f[i + j]) {
				f[i] = hsh; break;
			}
		}
	}
	for (int i = 0; i <= n - 1; i += SZ(mp[f[i]])) cout << mp[f[i]] << " ";
}
signed main() {
	IOS;
	int T = 1;
	// qio >> T;
	while (T--) solve();
}

思路二:

#include <bits/stdc++.h>
// #define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 1e4 + 10, M = 1e6 + 10;
int n, m, tot;
string ori, w[M];
vector<int> ans;
struct rec {
	int son[26], flag;
} tr[M];
void build(string s, int id) {
	int p = 0;
	for (int i = 0; i < SZ(s); ++i) {
		int c = s[i] - 'a';
		if (tr[p].son[c] == 0)	tr[p].son[c] = ++tot;
		p = tr[p].son[c];
	}
	tr[p].flag = id;
}
bool dfs(int pos) {
	if (pos >= SZ(ori)) return true;
	int p = 0;
	for (int i = pos; i < SZ(ori); ++i) {
		int c = ori[i] - 'a';
		if (tr[p].son[c] == 0) break;
		p = tr[p].son[c];
		if (tr[p].flag != 0 && dfs(i + 1)) return ans.emplace_back(tr[p].flag), true;
	}
	return false;
}
void solve() {
	cin >> n >> ori >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> w[i];
		auto t = w[i];
		reverse(all(t));
		for (auto &c : t) if (c < 'a') c += 32;
		build(t, i);
	}
	dfs(0);
	for (int i = SZ(ans) - 1; i >= 0; --i) cout << w[ans[i]] << " ";
}
signed main() {
	IOS;
	int T = 1;
	// qio >> T;
	while (T--) solve();
}