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

<dl id="gekos"></dl>

<samp id="gekos"><em id="gekos"></em></samp>

<tfoot id="gekos"><delect id="gekos"></delect></tfoot>

<li id="gekos"><input id="gekos"></input></li>

<abbr id="gekos"></abbr>

<abbr id="gekos"></abbr>

<tfoot id="gekos"></tfoot>

<dl id="gekos"></dl>

<button id="gekos"></button>

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 巫閱讀(420) 評論(0) 編輯收藏引用所屬分類: 字符串處理

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: POJ 2408--Anagram Groups Pku 3080--Blue Jeans(暴力枚舉 + KMP) Pku 3630--Phone List(Trie) Pku 2503--Babelfish(Trie) Pku 1816--Wild Words(Trie + DFS) Pku 2513--Colored Sticks（Trie） Pku 2774--Long Long Message（后綴數組） Pku 2774--Long Long Message（后綴樹）

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

久久久久免费看成人影片| 国产99久久久久久免费看| 久久天天躁夜夜躁狠狠躁2022| 亚洲欧美另类日本久久国产真实乱对白| 成人精品一区二区久久| 久久国产免费直播| 91性高湖久久久久| 久久婷婷五月综合国产尤物app| 国产精品久久久久jk制服| 久久久中文字幕| 99久久夜色精品国产网站| 伊人久久大香线蕉影院95| 久久99精品久久久久久久不卡| 国产日韩久久免费影院| 亚洲国产成人久久笫一页| 久久精品aⅴ无码中文字字幕不卡| 精品久久久久久国产免费了| 久久精品中文闷骚内射| 伊人久久无码精品中文字幕| 国内精品人妻无码久久久影院| 久久精品国产亚洲αv忘忧草| 久久国产成人午夜aⅴ影院| 国产精品久久久天天影视| 久久久久久久精品妇女99| 日韩十八禁一区二区久久| A级毛片无码久久精品免费| 97精品国产91久久久久久| 无码日韩人妻精品久久蜜桃 | 99久久精品国产一区二区| 久久成人18免费网站| 国产精品激情综合久久| 久久天天躁狠狠躁夜夜96流白浆 | 91久久精品无码一区二区毛片| 99久久er这里只有精品18| 亚洲伊人久久大香线蕉综合图片| 污污内射久久一区二区欧美日韩| 久久97久久97精品免视看秋霞| 成人亚洲欧美久久久久| 久久国产V一级毛多内射| 三级片免费观看久久| 热RE99久久精品国产66热|

<tfoot id="asccs"></tfoot>