#include#include#include#include#include#include#include#include#include#include

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

統計難題

系統 1630 0

http://acm.hdu.edu.cn/showproblem.php?pid=1251

通過這道題學習一下Trie字典樹.

      #include <iostream>
      
        

#include 
      
      <fstream>
      
        

#include 
      
      <vector>
      
        

#include 
      
      <
      
        string
      
      >
      
        

#include 
      
      <algorithm>
      
        

#include 
      
      <map>
      
        

#include 
      
      <stack>
      
        

#include 
      
      <cmath>
      
        

#include 
      
      <queue>
      
        

#include 
      
      <
      
        set
      
      >
      
        

#include 
      
      <list>
      
        

#include 
      
      <cctype>
      
        

#include 
      
      <stdio.h>
      
        

#include 
      
      <stdlib.h>
      
        

#include 
      
      <
      
        string
      
      .h>


      
        #define
      
       REP(i,j,k) for(int i = j ; i < k ; ++i)


      
        #define
      
       MAXV (1000)


      
        #define
      
       INF (0x6FFFFFFF)


      
        #define
      
       MAX 26


      
        using
      
      
        namespace
      
      
         std;

typedef 
      
      
        struct
      
      
         Trie

{

    Trie 
      
      *
      
        next[MAX];

    
      
      
        int
      
       v;
      
        //
      
      
        這里表示該字符前綴出現的次數
      
      
        };

Trie 
      
      *
      
        root;




      
      
        void
      
       Insert(
      
        char
      
       *
      
        str)

{

    Trie 
      
      *current =
      
         root;

    
      
      
        int
      
        len=
      
        strlen(str);

    
      
      
        if
      
      (len==
      
        0
      
      ) 
      
        return
      
      
         ;

    REP(i,
      
      
        0
      
      
        ,len)

    {

        
      
      
        //
      
      
        若節點存在,則直接訪問下一個節點,并此前綴出現次數+1
      
      
        if
      
      (current->next[str[i]-
      
        '
      
      
        a
      
      
        '
      
      ]!=
      
        NULL)

        {

            current
      
      =current->next[str[i]-
      
        '
      
      
        a
      
      
        '
      
      
        ];

            current
      
      ->v++
      
        ;

        }

        
      
      
        //
      
      
        若節點不存在,則新建節點并初始化
      
      
        else
      
      
        

        {

            current
      
      ->next[str[i]-
      
        '
      
      
        a
      
      
        '
      
      ]=(Trie*)malloc(
      
        sizeof
      
      
        (Trie));

            current
      
      =current->next[str[i]-
      
        '
      
      
        a
      
      
        '
      
      
        ];

            REP(i,
      
      
        0
      
      ,
      
        26
      
      ) current->next[i]=
      
        NULL;

            current
      
      ->v=
      
        1
      
      
        ;

        }

    }

}


      
      
        int
      
       Find(
      
        char
      
       *
      
        str)

{

    
      
      
        int
      
       len=
      
        strlen(str);

    
      
      
        struct
      
       Trie *current=
      
        root;

    
      
      
        if
      
      (len==
      
        0
      
      ) 
      
        return
      
      
        0
      
      
        ;

    REP(i,
      
      
        0
      
      
        ,len)

    {

        
      
      
        //
      
      
        如果關鍵詞本字符存在,則訪問下一個節點
      
      
        if
      
      (current->next[str[i]-
      
        '
      
      
        a
      
      
        '
      
      ]!=
      
        NULL)

            current
      
      =current->next[str[i]-
      
        '
      
      
        a
      
      
        '
      
      
        ];

        
      
      
        else
      
      
        return
      
      
        0
      
      ;
      
        //
      
      
        不存在直接返回0
      
      
            }

    
      
      
        return
      
       current->v;
      
        //
      
      
        返回該前綴出現次數
      
      
        }


      
      
        void
      
      
         Init()

{

    root
      
      =(Trie *)malloc(
      
        sizeof
      
      
        (Trie));

    REP(i,
      
      
        0
      
      ,
      
        26
      
      ) root->next[i]=
      
        NULL;

    root
      
      ->v=
      
        1
      
      
        ;

}


      
      
        int
      
      
         main()

{

    Init();

    
      
      
        char
      
       str[
      
        11
      
      
        ];

   
      
      
        //
      
      
         freopen("in.txt","r",stdin);
      
      
        while
      
      (gets(str)&&strcmp(str,
      
        ""
      
      )!=
      
        0
      
      
        )

            Insert(str);

    
      
      
        char
      
       tmp[
      
        11
      
      
        ];

    
      
      
        while
      
      (~scanf(
      
        "
      
      
        %s
      
      
        "
      
      
        ,tmp))

        printf(
      
      
        "
      
      
        %d\n
      
      
        "
      
      
        ,Find(tmp));

    
      
      
        return
      
      
        0
      
      
        ;

}
      
    

?

統計難題


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。?!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 欧美激情精品久久久久久不卡 | 天天操穴| 操操网站 | 97免费视频免费视频 | 欧美日韩乱码毛片免费观看 | 国产主播在线看 | 精品国产一区二区三区四区不 | 久久久99精品 | 伊人久久精品线影院 | 人人爽天天爽 | 成人国产视频在线观看 | 伊人成人在线观看 | 清纯唯美亚洲综合日韩第 | 久久成年人视频 | 五月婷婷视频在线观看 | 久热爱免费精品视频在线播放 | 一级毛片在线 | 久草免费在线 | 黄色片网站在线免费观看 | 亚洲va欧美va人人爽夜夜嗨 | 精品久久久久久午夜 | 香蕉视频免费在线观看 | 很黄的网站在线观看 | 免费成人黄色 | 国产成人亚洲综合无 | 中文字幕亚洲精品日韩精品 | 成人久久免费视频 | 亚洲欧洲一区二区三区在线观看 | 男人的天堂在线视频 | 国产手机精品一区二区 | 免费观看一级成人毛片软件 | 国产欧美综合一区二区 | 国产大片免费观看中文字幕 | 欧美在线一区视频 | 五月在线视频 | 奇米久久| 夭天干夜夜怕 | 日日欧美 | 日韩波多野结衣 | 国产精品午夜性视频 | www.91在线观看|