• <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久久人人爽亚洲精品美女|
精品水蜜桃久久久久久久|
久久精品极品盛宴观看|
国内精品久久久久|
狠狠色丁香久久婷婷综合图片
|
久久人人爽人人爽人人片AV东京热|
久久中文字幕人妻熟av女|
久久精品国产亚洲av影院|
人妻丰满?V无码久久不卡|
国产精品久久99|
午夜精品久久久久久久|
欧美一级久久久久久久大片|
东京热TOKYO综合久久精品|
久久夜色精品国产亚洲|
精品人妻伦一二三区久久|
国内精品久久久久久久97牛牛|
亚洲日韩欧美一区久久久久我|
精品免费tv久久久久久久|
久久久久av无码免费网|
久久久久无码精品|
99久久www免费人成精品|
成人免费网站久久久|
看久久久久久a级毛片|
久久精品国产亚洲av麻豆图片|
久久亚洲av无码精品浪潮|
国产精品九九久久免费视频|
狠狠色丁香婷婷久久综合不卡|
久久人妻少妇嫩草AV无码专区|
99久久国产亚洲综合精品|
伊人色综合九久久天天蜜桃|
亚洲午夜精品久久久久久app|
久久久久亚洲AV无码去区首|
久久www免费人成精品香蕉|
久久91精品综合国产首页|
久久国产精品免费一区|
人妻丰满?V无码久久不卡|
久久婷婷午色综合夜啪|
思思久久99热只有频精品66|
亚洲精品乱码久久久久久久久久久久
|