題目
對(duì)于這到題目很容易看出是一個(gè)多字符串匹配問(wèn)題 顯然是要用到trie圖
不過(guò)這個(gè)題目要求將所有定式 一次trie恐怕是做不了了
難道要用其他的方法么 雖然單純的trie無(wú)法滿足題目要求 但是沒(méi)有比他再像的了
繼續(xù)思考trie圖可以完成的事將所有匹配成功的位置以及與誰(shuí)匹配返回
但是每個(gè)匹配成功的位置只能返回一個(gè) 與其成功匹配的字符串 顯然這會(huì)有遺漏
比如
dd
bbdd
去匹配bbdd則最多只會(huì)有一個(gè)被記錄
顯然如果一個(gè)兩個(gè)串需要同時(shí)被記錄當(dāng)且僅當(dāng)一個(gè)串是另一個(gè)串的后綴并且較長(zhǎng)串被匹配
所以每次記錄長(zhǎng)度最長(zhǎng)的字符串即可
在這次匹配之后建一顆trie將所有字符串的逆串插入
查找所有被記錄的字符串將路徑上所有的字符串記錄即可