gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
#include <stdio.h>
#include 
<string>
#include 
<algorithm>
using namespace std ;

struct WORD    
{
    
int ID ;    //模式串编号,处理重复
    WORD *next ;
}
 ;

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

WORD g_Temp[MAXN];
int g_pos ;

const int CAP = 28 ;
typedef 
struct NODE    //Trie 节点
{    
    NODE()
    
{
        m_Pos.next 
= NULL ;
        current 
= &m_Pos ;
        memset(next, NULL, 
sizeof(NODE));
    }
;
    NODE 
*next[CAP];
    WORD m_Pos ;        
//处理重复
    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 
*= 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 ;
        }

        
//遇到'*',将当前位置到结束符的字符一个一个匹配
        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 阅读(401) 评论(0)  编辑 收藏 引用 所属分类: 字符串处理

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理