学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2846
* 求前缀所能匹配的单词的个数,可以是匹配单词的任意子串
* abcd 和这个串匹配的可以是 a，b，c，d，ab，cd，bcd。。。
* 所以可以将一个串拆成多个串的分割进行插入：abcd，bcd，cd，d
* 由于abab，和其子串ab会产生重复的计数，所以应该做标记，
*
*/
#include<stdio.h>
#include<string.h>
const int N=500000 ;
struct dic 
{
    int next[26];
    int pass ;
    int inid ;
    int val ;
}
node[N];
int num ;
void subinsert(char*str,int beg,int si)
{
    int pos=0,id ;
    for(int i=beg;str[i];i++)
    {
        id=str[i]-'a' ;
        if(node[pos].next[id]==0)
        node[pos].next[id]=++num ;
        pos=node[pos].next[id];
        //如果之前已经计数了，则本次插入不进行计数
        if(node[pos].inid==si)continue ;
        node[pos].inid=si ;
        node[pos].pass++;
    }
    node[pos].val=1 ;
    //存有单词结束
}
//abcd分成多个串：abcd，bcd，cd，d；
void insert(char*str,int si)
{
    for(int i=0;str[i];i++)
    {
        subinsert(str,i,si);
    }
}
//查找匹配的个数
void search(char*str)
{
    int pos=0,id ;
    for(int i=0;str[i];i++)
    {
        id=str[i]-'a' ;
        if(node[pos].next[id]==0)
        {
            printf("0\n");
            return ;
        }
        pos=node[pos].next[id];
    }
    printf("%d\n",node[pos].pass);
}

int main()
{
    int p,q,i ;
    char str[30];
    freopen("d:\\1.txt","r",stdin);
    scanf("%d",&p);
    memset(node,0,sizeof(node));
    num=0 ;
    for(i=0;i<p;i++)
    {
        scanf("%s",str);
        insert(str,i+1);
    }
    scanf("%d",&q);
    for(i=0;i<q;i++)
    {
        scanf("%s",str);
        search(str);
    }
    
    return 0 ;
}

有关字典树的更多内容见：

http://hi.baidu.com/tag/%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A--%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%26%2347%3Bstl/feeds

这个博客相当不错，各种数据结构的实现都有，可以参考其中的代码进行一些阅读，有助于提高。