pku 1816 Wild Words

时间：2011-05-15 来源：奋斗青春

字典树+深搜。。

这个题和hdu上的T9有点相似，不过应该比那个要稍难一点，这个需要处理？和*的情况，还要处理模式串相同的情况。。

这是我们前几天比赛的题目，当时没有做出来，开始的时没有想起来用字典树，后来队友说用字典树就写了一下。

写着写着感觉还可以，把？和*分别看成是next的第26和27，建树的时候很简单。之后查询的时候要考虑全面，

对于*进行特殊的处理，它可能是一个字符也可能是多个字符也可能没有字符。。

还有一点就是对于相同的模式串，要标记一下。

例如

2 1

abc

刚开始的时候把temp->num=-1;

Insert第0个模式串的时候把当前的temp->num=0;

之后插入第一个的时候把father[1]=0;然后把temp->num=1;这样就构成了一个线性的链了。

查询结束的时候按线性查找所有的数都加入到数组里面，对数组排序即可。

代码：

# include<stdio.h>
# include<string.h>
# include<stdlib.h>
# define MAX 28
struct Trie{
        int num;
        Trie *next[MAX];
};
char keyword[10];
char str[25];
int count[400005],k,father[100005],len;
int cmp(const void *a,const void *b)
{
        return *(int *)a - *(int *)b;
}
Trie *NewTrie()
{
        int i;
        Trie *temp=new Trie;
        temp->num=-1;
        for(i=0;i<MAX;i++)
                temp->next[i]=NULL;
        return temp;
}
void Insert(Trie *p,char s[],int ans)
{
        int i;
        Trie *temp=p;
        i=0;
        while(s[i])
        {
                if(s[i]>='a' && s[i]<='z') 
                {
                        if(temp->next[s[i]-'a']==NULL) temp->next[s[i]-'a']=NewTrie();
                        temp=temp->next[s[i]-'a'];
                }
                else
                {
                        if(s[i]=='?')
                        {
                                if(temp->next[26]==NULL) temp->next[26]=NewTrie();
                                temp=temp->next[26];
                        }
                        else 
                        {
                                if(temp->next[27]==NULL) temp->next[27]=NewTrie();
                                temp=temp->next[27];
                        }
                }
                i++;
        }
        if(temp->num==-1) temp->num=ans;
        else
        {
                father[ans]=temp->num;
                temp->num=ans;
        }
}
void dfs(Trie *p,int i)
{
        int j;
        Trie *temp=p;
        if(str[i]==0) 
        {
                if(temp->num!=-1)
                {
                        k++;
                        count[k]=temp->num;
                }
                while(temp->next[27]!=NULL ) 
                {
                        if(temp->next[27]->num!=-1)
                        {
                        k++;
                        count[k]=temp->next[27]->num;
                        }
                        temp=temp->next[27];
                }
                return;
        }

        if(temp->next[str[i]-'a']!=NULL) dfs(temp->next[str[i]-'a'],i+1);
        if(temp->next[26]!=NULL) dfs(temp->next[26],i+1);
        if(temp->next[27]!=NULL)
        {
                for(j=i;j<=len;j++)
                        dfs(temp->next[27],j);
        }
        
}
int main()
{
        int i,n,m,j,ans;
        Trie *p;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
        p=NewTrie();
        for(i=0;i<=n;i++)
                father[i]=i;
        for(i=0;i<n;i++)
        {
                scanf("%s",keyword);
                Insert(p,keyword,i);
        }
        while(m--)
        {
                scanf("%s",str);
                len=strlen(str);
                k=0;
                dfs(p,0);
                if(k==0) printf("Not match\n");
                else
                {
                        ans=k;
                        for(i=1;i<=ans;i++)
                        {
                                j=count[i];
                                while(father[j]!=j)
                                {
                                        k++;
                                        count[k]=father[j];
                                        j=father[j];
                                }
                        }
                        qsort(count+1,k,sizeof(count[1]),cmp);
                        count[0]=-1;
                        for(i=1;i<=k;i++)
                        {
                                if(count[i]!=count[i-1])
                                        printf("%d ",count[i]);
                        }
                        printf("\n");
                }       
        }
        }
        return 0;
}