Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
雁过留声——在字典树上dfs很好的一题!在字典树上dfs。 把模式串建字典树,然后匹配的时候: 如果当前节点的字符是字母,那就按一般字典树匹配的方法走。 如果当前节点的字符是'?',那就不管当前待匹配字是什么都走。 如果当前节点是‘*’,那有3种选择: 1.跳过当前节点 2.同'?' 3.跳过当前匹配字 为了省memory,我用了左孩子右兄弟的方法,但是带来了一个WA。 提供一些测试数据吧! 5 1 t t* t** t*** t**** the (继续匹配*!) 6 1 * ** *** **** ***** ****** abcdefghijabcdefghij (想通过上面这个数据需要trick。) 2 1 ? ** aca 2 1 ** ? aca (左孩子右兄弟的需要注意这个数据,看好你的*处理策略!) 5 2 *abca a?bca ab*ca abc*a abca* abca aabca (注意读题) Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator