题目
对于这到题目很容易看出是一个多字符串匹配问题 显然是要用到trie图
不过这个题目要求将所有定式 一次trie恐怕是做不了了
难道要用其他的方法么 虽然单纯的trie无法满足题目要求 但是没有比他再像的了
继续思考trie图可以完成的事将所有匹配成功的位置以及与谁匹配返回
但是每个匹配成功的位置只能返回一个 与其成功匹配的字符串 显然这会有遗漏
比如
dd
bbdd
去匹配bbdd则最多只会有一个被记录
显然如果一个两个串需要同时被记录当且仅当一个串是另一个串的后缀并且较长串被匹配
所以每次记录长度最长的字符串即可
在这次匹配之后建一颗trie将所有字符串的逆串插入
查找所有被记录的字符串将路径上所有的字符串记录即可
posted on 2009-03-12 03:21
250 阅读(1051)
评论(0) 编辑 收藏 引用 所属分类:
oi