gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 1816--Wild Words(Trie + DFS)
#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 *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 ;
        }
        //遇到'*',将当前位置到结束符的字符一个一个匹配
        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 巫 阅读(386) 评论(0)  编辑 收藏 引用 所属分类: 字符串处理

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