hdu 2846 【字典树】单词子串的匹配数

小咪咪 2022-05-25 14:27 32阅读 0赞

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][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]

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

[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]: 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