• <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>
            

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
            #include <stdio.h>
            #include             <string>
            #include             <algorithm>
            using namespace std ;

            struct WORD    
            {
                            int ID ;    //模式串編號，處理重復(fù)
                WORD *next ;
            }             ;

            const int MAXN = 100001 ;
            const int MAXM = 101 ;
            int N, M ;
            int match[MAXN] , num ;    //保存匹配結(jié)果
            char words[MAXM][25] ;

            WORD g_Temp[MAXN];
            int g_pos ;

            const int CAP = 28 ;
            typedef             struct NODE    //Trie 節(jié)點(diǎn)
            {    
                NODE()
                            {
                    m_Pos.next             = NULL ;
                    current             = &m_Pos ;
                    memset(next, NULL,             sizeof(NODE));
                }            ;
                NODE             *next[CAP];
                WORD m_Pos ;                    //處理重復(fù)
                WORD *current ;
            }            NODE;

            const int MEMORY = 30000 ;
            NODE memory[MEMORY] ;
            class BTree
            {
            public:
                BTree()
                            {
                    index             = 1;
                    head             = &memory[0];
                }                
                            void Insert(char *str, const int& w)
                            {
                                int len = (int)strlen(str);
                    NODE             *pt = head ;
                                for (int i = 0; i < len; ++i)
                                {
                                    if ( str[i] == '*' )
                                    {
                                        if ( pt->next[26] == NULL )
                                        {
                                pt            ->next[26] = &memory[index++] ;
                            }
                            pt             = pt->next[26] ;        
                            
                        }
                                    else if ( str[i] == '?' )
                                    {
                                        if ( pt->next[27] == NULL )
                                        {
                                pt            ->next[27] = &memory[index++] ;
                            }
                            
                            pt             = pt->next[27] ;
                        }
                                    else {
                                        if (pt->next[str[i]-'a'] == NULL)
                                        {
                                pt            ->next[str[i]-'a'] = &memory[index++];
                            }
                            
                            pt             = pt->next[str[i]-'a'];
                        }
                    }
                                //記錄模式串編號
                    if ( pt->m_Pos.next == NULL )
                        pt            ->current = &pt->m_Pos ;
                    g_Temp[g_pos].ID             = w ;
                    g_Temp[g_pos].next             = NULL ;
                    pt            ->current->next = &g_Temp[g_pos++] ;
                    pt            ->current = pt->current->next ;
                    
                }
                
                            void DFS( NODE *ptr, const int& pos , int w )
                            {
                                if ( words[pos][w] == '\0' )
                                {
                        WORD             *p = ptr->m_Pos.next ;
                                    while ( p ){
                            match[num]             = p->ID ;
                            num            ++ ;
                            p             = p->next ;
                        }

                                    while ( ptr->next[26] )
                            ptr             = ptr->next[26] ;
                        p             = ptr->m_Pos.next ;
                                    while ( p ){
                            match[num]             = p->ID ;
                            num            ++ ;
                            p             = p->next ;
                        }
                                    return ;
                    }
                                //遇到'*',將當(dāng)前位置到結(jié)束符的字符一個一個匹配
                    if ( ptr->next[26] != NULL )
                                {
                                    for ( int i = w ; i <= strlen(words[pos]) ; ++i )
                                    {
                            DFS( ptr            ->next[26], pos, i ) ;
                        }
                    }
                                //遇到'?'或字母，直接跳到下一個
                    if ( ptr->next[27] != NULL )
                                {
                        DFS( ptr            ->next[27], pos, w + 1 ) ;
                    }
                                if ( ptr->next[words[pos][w] - 'a'] != NULL )
                                {
                        DFS( ptr            ->next[words[pos][w] - 'a'], pos, w + 1 ) ;
                    }
                }
                
            public:
                NODE             *head;
                            int index;
            }            ;

            void Init()
            {
                g_pos             = 0 ;
            }

            int main()
            {    
                            int i ;
                            char tempstr[22] ;
                BTree trie ;
                scanf(            "%d %d", &N, &M) ;
                Init() ;
                
                            for ( i = 0 ; i < N ; ++i )
                            {
                    scanf(            "%s", &tempstr) ;
                    trie.Insert(tempstr, i) ;
                }
                            for ( i = 0 ; i < M ; ++i )
                            {
                    scanf(            "%s", &words[i]) ;    
                    num             = 0 ;
                    trie.DFS( trie.head, i,             0 ) ;
                    
                                if ( num == 0 )
                                {
                        printf(            "Not match\n") ;
                    }
                                else {
                        sort( match, match             + num ) ;
                        printf(            "%d ", match[0]) ;
                                    for ( int j = 1 ; j < num ; ++j )
                                    {
                                        if ( match[j] != match[j - 1] )
                                printf(            "%d ", match[j]) ;
                        }
                        printf(            "\n") ;
                    }
                }
                
                            return 0 ;
            }
            

	
            
	
	
            
		posted on 2008-11-09 17:05 巫 閱讀(407) 評論(0)  編輯 收藏 引用  所屬分類: 字符串處理 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



18岁日韩内射颜射午夜久久成人|
国产三级观看久久|
激情五月综合综合久久69|
99精品久久精品一区二区|
久久无码AV中文出轨人妻|
久久亚洲精品无码VA大香大香|
性高朝久久久久久久久久|
久久综合九色综合欧美就去吻|
三级韩国一区久久二区综合|
国产视频久久|
欧美日韩精品久久久久|
18禁黄久久久AAA片|
色欲久久久天天天综合网|
亚洲国产精品久久久天堂|
精品无码久久久久久尤物|
色综合久久综合网观看|
精品久久久久久久久久久久久久久
|
欧美激情一区二区久久久|
一级做a爰片久久毛片免费陪|
免费久久人人爽人人爽av|
香蕉久久夜色精品升级完成|
国产麻豆精品久久一二三|
99热都是精品久久久久久|
伊人久久亚洲综合影院|
久久夜色精品国产噜噜亚洲AV
|
99精品国产综合久久久久五月天
|
一级做a爰片久久毛片人呢|
九九热久久免费视频|
影音先锋女人AV鲁色资源网久久
|
亚洲国产成人久久精品99|
久久国产色AV免费观看|
国产激情久久久久影院|
国产成人精品三上悠亚久久|
狠狠干狠狠久久|
国产精品久久久久久五月尺|
狠狠色丁香久久综合婷婷|
亚洲第一永久AV网站久久精品男人的天堂AV|
亚洲AV成人无码久久精品老人|
亚洲欧美日韩精品久久|
欧洲精品久久久av无码电影|
久久99精品久久久久久9蜜桃|