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