uva 1462 - Fuzzy Google Suggest(字典树+dfs)

题目链接:uva 1462 - Fuzzy Google Suggest

题目大意:模拟google的模糊搜索,给定给一个字符串集合,然后有n次搜索,每次有一个整数x和一个字符串,表示可以对字符串进行x次修改,包括增加、修改和删除一个字符,问修改后的字符可能是字符集中有多少个字符串的前缀。

解题思路:先建立字典树,对于每次搜索,在字典树上进行dfs,根据参数x和字符串匹配的位置进行处理,对于匹配到末尾的位置标记为2,然后对于第二次dfs,搜索每个分支上最早出现2的位置即可。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 3000005;
const int sigma_size = 26;

struct Tire {
    int sz;
    int g[maxn][sigma_size];
    int val[maxn], vis[maxn];

    int deep, ans;
    char s[15];

    void init();
    int idx(char ch);
    void insert(char* str);
    int solve(char* str, int x);
    void dfs(int u, int d, int x);
    void clear(int u, int flag);
}AC;

int main () {
    int n, x;
    char str[15];
    while (scanf("%d", &n) == 1) {
        AC.init();

        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            AC.insert(str);
        }

        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%s%d", str, &x);
            printf("%d\n", AC.solve(str, x));
        }
    }
    return 0;
}

void Tire::init() {
    sz = 1;
    val[0] = 0;
    //memset(vis, 0, sizeof(vis));
    memset(g[0], 0, sizeof(g[0]));
}

int Tire::idx (char ch) {
    return ch - ‘a‘;
}

void Tire::dfs (int u, int d, int x) {
    if (x < 0)
        return;

    if (vis[u] == 0)
        vis[u] = 1;

    if (d == deep) {
        vis[u] = 2;
        return;
    }

    int v = idx(s[d]);
    if (g[u][v])
        dfs(g[u][v], d + 1, x);

    dfs(u, d + 1, x - 1);

    for (int i = 0; i < sigma_size; i++) {
        if (g[u][i]) {
            dfs(g[u][i], d, x - 1);
            dfs(g[u][i], d + 1, x - 1);
        }
    }
}

void Tire::clear(int u, int flag) {
    if (vis[u] == 0)
        return;

    if (flag && vis[u] == 2) {
        ans += val[u];
        flag = 0;
    }

    for (int i = 0; i < sigma_size; i++) {
        if (g[u][i])
            clear(g[u][i], flag);
    }
    vis[u] = 0;
}

int Tire::solve(char* str, int x) {
    ans = 0;
    deep = strlen(str);
    strcpy(s, str);

    dfs(0, 0, x);
    clear(0, 1);
    return ans;
}

void Tire::insert(char* str) {
    int u = 0, n = strlen(str);

    for (int i = 0; i < n; i++) {
        int v = idx(str[i]);

        if (g[u][v] == 0) {
            val[sz] = 0;
            memset(g[sz], 0, sizeof(g[sz]));
            g[u][v] = sz++;
        }

        u = g[u][v];
        val[u]++;
    }
}
时间: 09-02

uva 1462 - Fuzzy Google Suggest(字典树+dfs)的相关文章

hdu1247Hat’s Words (组合单词,字典树+DFS)

Problem Description A hat's word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary. You are to find all the hat's words in a dictionary. Input Standard input consists of a number of lowercase words, on

hdu1298 T9(手机输入法,每按一个数字,找出出现频率最高的字串,字典树+DFS)

Problem Description A while ago it was quite cumbersome to create a message for the Short Message Service (SMS) on a mobile phone. This was because you only have nine keys and the alphabet has more than nine letters, so most characters could only be

hdu 1298 T9(字典树+DFS)

题目连接:hdu 1298 T9 题目大意:模拟手机打字的猜想功能,根据概率,每按一个按键,输出可能性最高的串.先给定N个单词,以及频率, 然后是Q次询问,每次询问给定一个按按键的顺序,以1为终止. 解题思路:对单词表建立字典树,每个节点有一个经过的频率,这个频率是根据所有经过该节点的单词频率总和.然后 DFS搜索一遍,将答案保存在ans中. #include <cstdio> #include <cstring> #include <algorithm> using

hust1350Trie【字典树+dfs || 字典树 + LCA】

大意:告诉你一些字符串 让你组成字典树, 然后定义每个节点到所有叶子节点的距离的和等于改点的value 当根节点只有一个孩子,该根节点也算一个叶子节点 问所有节点的value的最小值 分析: 开始做的时候  就想的是   枚举每个点  然后求它到所有叶子节点的和  求任意两点的最近距离  用公共祖先来求 于是就有了这个算法 需要预处理出来所有的叶子节点 不能单纯的用字典树的flag来记录  例如插入aaa aa a  那么 a  aa aaa 都会被当成叶子节点 对于这里的处理 我是排了一次序

HDU 1298 T9(字典树+dfs)

http://acm.hdu.edu.cn/showproblem.php?pid=1298 题意:模拟手机9键,给出每个单词的使用频率.现在给出按键的顺序,问每次按键后首字是什么(也就是要概率最大的). 思路: 先建立字典树算出每个前缀出现的概率,然后dfs每种情况,选择概率大的. 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int

UVA 11488 Hyper Prefix Sets 字典树

模板题,字典树最基本的操作 在看别人的板子的时候学到了一点小技巧 下面贴AC代码,顺便补一补字典树相关,顺便放一下橙子讲课的笔记 Trie三兄弟--标准Trie.压缩Trie.后缀Trie 字符串模式匹配算法--BM.Horspool.Sunday.KMP.KR.AC算法一网打尽 #include<bits/stdc++.h> using namespace std; const int MAX = 5e4 + 5; string s; int n, t, ans; struct Trie {

UVA 3942 -- Remember the Word (字典树+dp)

Remember the Word Neal is very curious about combinatorial problems, and now here comes a problem about words. Knowing that Ray has a photographic memory and this may not trouble him, Neal gives it to Jiejie. Since Jiejie can't remember numbers clear

LintCode 单词搜索Ⅱ 字典树

今天做了道有意思的题目,题目要解出来不难,但看到他的提示 发现这道题我一开始并没有用到字典树 然后就使用字典树+DFS写了一遍,也算是巩固下字典树的相关知识 题目:原题地址 给出一个由小写字母组成的矩阵和一个字典.找出所有同时在字典和矩阵中出现的单词.一个单词可以从矩阵中的任意位置开始,可以向左/右/上/下四个相邻方向移动. 样例 给出矩阵: doafagaidcan 和字典: {"dog", "dad", "dgdg", "can&q

uva 1385 - Billing Tables(字典树)

题目链接:uva 1385 - Billing Tables 题目大意:给定n个电话前缀,每个前缀是一个区域的前缀,现在要生成一个新的电话单,即对于每个电话号码,从旧的电话单上从前向后遍历,如果出现前缀匹配,则该电话号码对应的即为当前的区号,要求生成的新电话单尽量小. 解题思路:用dfs建立字典树,在区间范围内的点对应均为对应的区号,注意如果70.71.72....79都为SB的话,那么可以合并成7,并且对应区号为SB. 注意合并的条件为区号相同即可,并不是说对应旧电话单匹配位置相同. 注意这组