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

            







            
	    
    




            






            

				

            






    
    







            
	   
	



国内精品九九久久精品|
国产 亚洲 欧美 另类 久久|
亚洲欧美成人久久综合中文网
|
日韩欧美亚洲综合久久|
伊人久久大香线蕉av一区|
久久99国产综合精品女同|
精品久久久久久久无码|
久久免费视频观看|
无遮挡粉嫩小泬久久久久久久|
99久久超碰中文字幕伊人|
久久人妻少妇嫩草AV无码蜜桃|
久久99国产精品久久|
中文字幕无码久久精品青草|
国产午夜久久影院|
伊人久久大香线蕉综合影院首页|
国内精品久久久久久久涩爱|
亚洲精品国精品久久99热一|
久久精品亚洲精品国产欧美|
99久久精品免费国产大片|
久久久久久久久久久|
国产成人精品久久亚洲|
97久久超碰国产精品2021|
日本精品一区二区久久久|
久久久久四虎国产精品|
日韩人妻无码精品久久免费一
|
日日躁夜夜躁狠狠久久AV|
亚洲国产成人乱码精品女人久久久不卡
|
亚洲国产精品无码久久一线
|
久久一区二区三区99|
91精品久久久久久无码|
色综合久久88色综合天天|
久久免费精品一区二区|
97久久综合精品久久久综合|
A级毛片无码久久精品免费|
久久久这里有精品|
日本加勒比久久精品|
亚洲国产成人精品久久久国产成人一区二区三区综
|
99久久香蕉国产线看观香|
精品久久久久久国产三级|
国产午夜精品久久久久九九电影|
免费国产99久久久香蕉|