首页 > 代码库 > UVA 1462 - Fuzzy Google Suggest(字典树+dfs)
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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。