本文主要是介绍UVA 1462 - Fuzzy Google Suggest(字典树+dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVA 1462 - Fuzzy Google Suggest
题目链接
题意：要模拟谷歌的模糊搜索，先有一些文本，然后每次输入一个单词查询，这个单词可以进行最多ti次操作，每次操作可以删除一个字符，修改一个字符，或增添一个字符，问这样这个单词最多可以匹配多少个前缀
思路：先建好字典树，每个结点保存经过的次数，然后每次查询，就在字典树上进行dfs，对于找到的结点标记为2，路径标记为1，然后利用这个标记，再进行一次dfs，找到2结点就终止，并且答案加上该位置的次数，由于结点有300W，数组不能直接清，所以还要再来一遍dfs清数组
代码：
#include <cstdio>
#include <cstring>
using namespace std;const int MAXNODE = 3000005;
const int SIGMA_SIZE = 26;int n, m, ti;
char str[15];struct Trie {int ch[MAXNODE][SIGMA_SIZE];int val[MAXNODE];int vis[MAXNODE];int sz;void init() {sz = 1; memset(ch[0], 0, sizeof(ch[0]));}int idx(char c) {return c - 'a';}void insert(char *str, int v) {int n = strlen(str);int u = 0;for (int i = 0; i < n; i++) {int c = idx(str[i]);if (!ch[u][c]) {memset(ch[sz], 0, sizeof(ch[sz]));val[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];val[u] += v;}}void dfs(int u, int len, int use) {if (len == n) {vis[u] = 2;return;}if (vis[u] == 0)vis[u] = 1;if (use < ti)dfs(u, len + 1, use + 1);for (int i = 0; i < SIGMA_SIZE; i++) {if (!ch[u][i]) continue;if (idx(str[len]) == i) dfs(ch[u][i], len + 1, use);else if (use < ti) dfs(ch[u][i], len + 1, use + 1);if (use < ti) dfs(ch[u][i], len, use + 1);}}int cal(int u) {if (vis[u] == 2)return val[u];int ans = 0;for (int i = 0; i < SIGMA_SIZE; i++) {if (!ch[u][i]) continue;if (vis[ch[u][i]])ans += cal(ch[u][i]);}return ans;}void clr(int u) {for (int i = 0; i < SIGMA_SIZE; i++) {if (!ch[u][i]) continue;if (vis[ch[u][i]]) clr(ch[u][i]);}vis[u] = 0;}void solve() {init();for (int i = 0; i < n; i++) {scanf("%s", str);insert(str, 1);}scanf("%d", &m);for (int i = 0; i < m; i++) {scanf("%s%d", str, &ti);n = strlen(str);dfs(0, 0, 0);printf("%d\n", cal(0));clr(0);}}} gao;int main() {while (~scanf("%d", &n)) {gao.solve();}return 0;
}这篇关于UVA 1462 - Fuzzy Google Suggest(字典树+dfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
