• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            #include <iostream>
            #include 
            <queue>

            using namespace std;

            struct Trie{
                
            int    cnt;
                Trie
            *  next[26], *prefix;
            }
            Table[500000];

            int   index= 0;
            Trie
            * root;
            char  str[1000001];

            void init(){
                index
            = 0;
                root
            = &Table[index];
                memset( Table[
            0].next, 0sizeof(Table[0].next) );
                Table[
            0].cnt= 0; Table[0].prefix= NULL;
            }


            void insert( char* s )
            {
                Trie
            * r= root;
                
            while*s ){
                    
            int t= *s- 'a';
                    
            if!r->next[t] ){
                        
            ++index;
                        memset( Table[index].next, 
            0sizeof(Table[index].next) );
                        Table[index].cnt
            = 0; Table[index].prefix= NULL;
                        r
            ->next[t]= &Table[index];
                    }

                    r
            = r->next[t]; s++;
                }
                
                r
            ->cnt++;
            }


            void get_prefix()
            {
                Trie
            * r= root;
                queue
            <Trie*> q;
                q.push( root ); root
            ->prefix= NULL;
                
                
            while!q.empty() ){
                    Trie
            * father= q.front(); q.pop();
                    
            forint i= 0; i< 26++i )
                    
            if( father->next[i] ){
                        Trie
            * tmp= father->prefix;
                        
            while( tmp && !tmp->next[i] ) tmp= tmp->prefix;
                        
            if!tmp ) father->next[i]->prefix= root;
                        
            else       father->next[i]->prefix= tmp->next[i];
                        
                        q.push( father
            ->next[i] );
                    }

                }

            }


            int ac_run(){
                Trie
            * p= root;
                
            int ans= 0;
                
            char* s= str;
                
            while*s ){
                    
            int t= *s- 'a';
                    
            while!p->next[t] && p!= root ) p= p->prefix;
                    p
            = p->next[t];
                    
            if!p ) p= root;
                    Trie
            * tp= p;
                    
            while( tp!= root && tp->cnt!= -1 ){
                        ans
            += tp->cnt; 
                        tp
            ->cnt= -1
                        tp
            = tp->prefix;}

                    s
            ++;
                }

                
            return ans;
            }


            int main()
            {
                
            int test;
                scanf(
            "%d",&test );
                
            while( test-- )
                
            {
                    
            int n; char s[55];
                    scanf(
            "%d",&n ); init(); getchar();
                    
            forint i= 0; i< n; ++i ){
                        gets(s); insert(s); }

                    gets(str); get_prefix();
                    printf(
            "%d\n", ac_run() );    
                }

                
                
            return 0;
            }

            posted on 2009-04-15 14:17 Darren 閱讀(382) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            超级97碰碰碰碰久久久久最新| 欧美日韩精品久久久久| 久久亚洲日韩看片无码| 久久精品国产欧美日韩99热| 免费精品久久天干天干| 粉嫩小泬无遮挡久久久久久| 久久国产精品久久| 午夜精品久久影院蜜桃| 青青草国产精品久久| 伊人久久大香线焦AV综合影院| 99久久99久久精品国产片果冻| 国产69精品久久久久观看软件| 久久久91精品国产一区二区三区| 亚洲国产高清精品线久久| 国产情侣久久久久aⅴ免费| 精品久久久久久无码国产| 久久久久AV综合网成人 | 久久受www免费人成_看片中文| 久久久精品国产sm调教网站| 久久综合亚洲色HEZYO社区| 久久99热这里只有精品国产| 99久久国产综合精品麻豆| 亚洲AV无码1区2区久久| 精品国产乱码久久久久软件| 色播久久人人爽人人爽人人片AV| 国产精品九九久久免费视频 | 久久精品国产亚洲av水果派 | 精品一久久香蕉国产线看播放| 国产精品久久国产精麻豆99网站| 久久久久久毛片免费播放| 久久人人爽人人爽人人AV东京热| 久久综合香蕉国产蜜臀AV| 人人狠狠综合久久亚洲婷婷| 国内精品久久国产大陆| 亚洲欧美国产精品专区久久| 久久91精品国产91久| 成人免费网站久久久| 一本久久a久久精品综合香蕉| 亚洲精品无码久久久久去q | 国产精品一区二区久久精品涩爱| A级毛片无码久久精品免费|