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

            







            
	    
    




            






            

				

            






    
    







            
	   
	



久久综合偷偷噜噜噜色|
久久久久久免费一区二区三区|
热re99久久精品国产99热|
狠狠狠色丁香婷婷综合久久俺|
日本精品久久久中文字幕|
欧美激情精品久久久久久久|
久久久久久久波多野结衣高潮|
97热久久免费频精品99|
久久影视综合亚洲|
国产情侣久久久久aⅴ免费|
99久久精品无码一区二区毛片
|
99久久精品国产一区二区蜜芽|
久久精品免费网站网|
色偷偷88888欧美精品久久久|
久久精品草草草|
亚洲av日韩精品久久久久久a|
99久久精品久久久久久清纯|
久久综合亚洲欧美成人|
亚洲国产一成久久精品国产成人综合
|
狠狠色丁香久久婷婷综合_中|
久久婷婷成人综合色综合|
理论片午午伦夜理片久久|
久久se精品一区二区|
99久久无色码中文字幕人妻|
久久久亚洲精品蜜桃臀|
青青热久久综合网伊人|
久久综合亚洲欧美成人|
伊人久久无码中文字幕|
婷婷久久综合九色综合绿巨人|
99久久精品免费看国产|
99久久精品国产一区二区|
亚洲国产精品一区二区久久|
99久久精品国产麻豆|
久久精品国产亚洲AV蜜臀色欲|
久久精品无码一区二区日韩AV|
品成人欧美大片久久国产欧美...
品成人欧美大片久久国产欧美
|
久久精品草草草|
国产精品美女久久久久av爽
|
久久精品国产亚洲AV嫖农村妇女|
久久青青草视频|
国产偷久久久精品专区|