• <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) 評論(0)  編輯 收藏 引用

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


            香蕉99久久国产综合精品宅男自 | 久久久WWW成人免费精品| 一本色道久久88加勒比—综合| 久久国产色AV免费观看| 青草影院天堂男人久久| 亚洲国产成人久久综合野外| 亚洲中文字幕无码一久久区| 精品国产乱码久久久久久郑州公司| 日本免费久久久久久久网站| 精品伊人久久久| 国产精品久久精品| 无码人妻久久一区二区三区蜜桃 | 久久久国产精品亚洲一区| 狠狠色综合久久久久尤物| 久久99精品久久久大学生| 色综合久久88色综合天天| 久久亚洲AV成人无码| 亚洲精品高清国产一久久| 久久免费视频1| 亚洲国产精品久久久久久| 无码超乳爆乳中文字幕久久| 久久久久香蕉视频| 久久夜色精品国产亚洲| 久久婷婷成人综合色综合| 亚洲国产成人久久笫一页| 久久久久久亚洲精品无码| 亚洲国产精品久久久久婷婷老年| 久久婷婷五月综合国产尤物app| 国产精品美女久久福利网站| 久久国产精品一区| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 亚洲va国产va天堂va久久| 欧美久久亚洲精品| 久久99亚洲综合精品首页| 欧美精品一区二区精品久久| 国产精品一区二区久久国产| 久久久久久久精品成人热色戒| 久久99九九国产免费看小说| 老司机午夜网站国内精品久久久久久久久 | 久久久久高潮综合影院| 久久人人爽人人爽人人爽|