• <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 
            <cstdio>
            #include 
            <cstdlib>
            #include 
            <queue>
            #include 
            <vector>

            using namespace std;

            struct Trie{
                
            int    cnt;
                Trie
            *  next[52], *prefix;
            }
            Table[1000000];

            int   idx,id;
            Trie
            * root;
            char  str[1000011];
            bool  visite[1010];
            vector
            <int> flag[1010];

            void init(){
                idx
            = 0; id= 1;
                root
            = &Table[idx];
                memset( Table[
            0].next, 0sizeof(Table[0].next) );
                Table[
            0].cnt= 0; Table[0].prefix= NULL;
                memset( visite, 
            falsesizeof(visite) );
            }


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

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

                
                
            if( r->cnt ) flag[r->cnt].push_back( id++ );
                
            else         r->cnt= id++;
            }


            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< 52++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] );
                    }

                }

            }


            void ac_run(){
                Trie
            * p= root;
                
            char* s= str;
                
            while*s ){
                    
            int t;
                    
            if*s>= 'a' && *s<= 'z' )t= *s- 'a';
                    
            if*s>= 'A' && *s<= 'Z' )t= *s- 'A'+ 26;
                    
            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!= 0 ){
                        visite[tp
            ->cnt]= true;
                        tp
            = tp->prefix;}

                    s
            ++;
                }

            }


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

                    get_prefix(); ac_run();
                    
            forint i= 1; i<= n; ++i )
                    
            if( visite[i] ){
                        
            for( size_t j= 0; j< flag[i].size(); ++j )
                        visite[ flag[i][j] ]
            = true;}

                    
            forint i=1; i<=n;++i)
                    
            if(visite[i])puts("y");
                    
            else puts("n");
                    
            for(int i= 0; i<= n; ++i ) flag[i].clear();
                }

                
                
            return 0;
            }

            posted on 2009-04-15 15:42 Darren 閱讀(525) 評論(0)  編輯 收藏 引用

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


            国产精品成人久久久| 国产亚州精品女人久久久久久| 综合久久一区二区三区| 99久久国产宗和精品1上映| 亚洲欧美伊人久久综合一区二区| 久久久久无码精品国产不卡| 久久综合丁香激情久久| 伊人 久久 精品| 女人香蕉久久**毛片精品| 亚洲国产婷婷香蕉久久久久久| 精品久久亚洲中文无码| 99热都是精品久久久久久| 久久永久免费人妻精品下载| 久久高潮一级毛片免费| 久久av无码专区亚洲av桃花岛| 久久精品中文字幕有码| 午夜天堂av天堂久久久| 久久狠狠一本精品综合网| 国产精品免费看久久久| 久久伊人五月丁香狠狠色| 久久se精品一区二区| 久久久久亚洲AV无码麻豆| 久久国产AVJUST麻豆| 久久精品国产亚洲精品| 久久这里只精品国产99热| 久久精品国产亚洲av麻豆色欲| 国产精品99久久久久久宅男小说| 国产精品美女久久久免费| 99精品国产在热久久| 久久99国产综合精品女同| 亚洲午夜久久久久久久久电影网 | 久久亚洲欧洲国产综合| 亚洲国产精品久久久久| 久久99国产精品久久99| 久久综合狠狠综合久久综合88| 精品久久久无码21p发布| 日韩人妻无码一区二区三区久久99| 久久精品国产72国产精福利| 久久久久人妻一区精品| 亚洲精品NV久久久久久久久久 | 精品久久久久久无码人妻热 |