題目
對于這到題目很容易看出是一個多字符串匹配問題 顯然是要用到trie圖
不過這個題目要求將所有定式 一次trie恐怕是做不了了
難道要用其他的方法么 雖然單純的trie無法滿足題目要求 但是沒有比他再像的了
繼續(xù)思考trie圖可以完成的事將所有匹配成功的位置以及與誰匹配返回
但是每個匹配成功的位置只能返回一個 與其成功匹配的字符串 顯然這會有遺漏
比如
dd
bbdd
去匹配bbdd則最多只會有一個被記錄
顯然如果一個兩個串需要同時被記錄當(dāng)且僅當(dāng)一個串是另一個串的后綴并且較長串被匹配
所以每次記錄長度最長的字符串即可
在這次匹配之后建一顆trie將所有字符串的逆串插入
查找所有被記錄的字符串將路徑上所有的字符串記錄即可
posted on 2009-03-12 03:21
250 閱讀(1075)
評論(0) 編輯 收藏 引用 所屬分類:
oi