• <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, 0, sizeof(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,             0, sizeof(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();
                                for( int 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();
                                for( int 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)  編輯 收藏 引用  
            

            







            
	    
    




            






            

				

            






    
    







            
	   
	



精品久久久久久无码不卡|
久久久久婷婷|
99久久婷婷国产综合亚洲|
色噜噜狠狠先锋影音久久|
精品视频久久久久|
亚洲精品无码久久一线|
 久久综合九色综合久99|
久久久久免费精品国产|
亚洲国产精品久久久久婷婷老年|
久久中文字幕无码专区|
久久精品天天中文字幕人妻|
久久成人永久免费播放|
久久精品www人人爽人人|
成人综合久久精品色婷婷|
国产激情久久久久影院老熟女|
日韩久久久久久中文人妻|
久久亚洲高清综合|
99热成人精品免费久久|
狠狠88综合久久久久综合网|
久久亚洲国产最新网站|
久久久久18|
久久国产影院|
久久久久18|
久久性生大片免费观看性|
久久国产乱子伦精品免费午夜|
狠狠色丁香婷婷久久综合不卡|
久久久久99精品成人片欧美|
久久久久青草线蕉综合超碰|
亚洲精品97久久中文字幕无码|
久久久久亚洲AV无码专区桃色|
亚洲国产精品久久66|
久久亚洲国产欧洲精品一|
国产精品久久久久无码av|
国产Av激情久久无码天堂|
狠狠干狠狠久久|
国产午夜福利精品久久|
国产亚洲精午夜久久久久久|
亚洲一区中文字幕久久|
久久国产美女免费观看精品
|
久久中文字幕人妻丝袜|
三级片免费观看久久|