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

68 阅读 0 评论 45 点赞

我是靠谱客的博主斯文云朵，最近开发中收集的这篇文章主要介绍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("%dn", 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]++;
    }
}