UVA4769 Trie树+剪枝

2013年11月18日 11点热度 0条评论 来源: 王的守护者

    很不错的一道字典树的题,把字典里的单词建成Trie树,每个节点维护一个以这个节点为根的子树有多少个单词,还有一个是当前节点有没有在这次询问中被搜索到,然后匹配的时候每次达到询问串的终点时把这个点标记一下,搜索过程中遇到的点也标记一下,然后再DFS一遍,这样保证不会搜索到字符串未遍历过的点,这个剪枝很重要。

     

#include<cstdio>
#include<iostream>
#include<cstring>
#include<set>
#define N 3000000
using namespace std;
char str[10000];
int cnt,l,phs;
int id[N],c[N],num[N],next[N][26],vis[N];
void insert(char *s)
{
    int i = 0,k = 0;
    num[k]++;
    while(s[i])
    {
        int id = s[i]-'a';
        if(!next[k][id])
        {
            next[k][id] = cnt++;
            memset(next[cnt-1],0,sizeof(next[cnt-1]));
        }
        k = next[k][id];
        num[k]++;
        i++;
    }
}
void dfs1(int ps,int u,int dep)
{
    if(dep<0||ps>l)return;
    vis[u] = phs;
    if(ps == l)c[u] = phs;
    dfs1(ps+1,u,dep-1);
    for(int i = 0;i<26;i++)
    {
        if(next[u][i] == 0)continue;
        int v = next[u][i];
        dfs1(ps,v,dep-1);
        if(str[ps]-'a'!=i)dfs1(ps+1,v,dep-1);
        else dfs1(ps+1,v,dep);
    }
}
int dfs2(int u)
{
    int tmp = 0;
    if(c[u] == phs)return num[u];
    if(vis[u]!=phs)return 0;;
    for(int i = 0;i<26;i++)
        if(next[u][i])
            tmp+=dfs2(next[u][i]);
    return tmp;
}
int main()
{
    int n,m,i,j,x;
    while(scanf("%d",&n)!=EOF)
    {
        cnt = 1;
        for(i = 0;i<N;i++)
            num[i] = c[i] = 0;
        for(i = 0;i<n;i++)
        {
            scanf("%s",str);
            insert(str);
        }
        scanf("%d",&m);
        for(i = 1;i<=m;i++)
        {
            phs = i;
            scanf("%s%d",str,&x);
            l = strlen(str);
            dfs1(0,0,x);
            printf("%d\n",dfs2(0));
        }
    }
    return 0;
}

    原文作者:王的守护者
    原文地址: https://blog.csdn.net/shllhsboa/article/details/16807793
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。