[理工] [資結] 97清大資工 Knuth algorithm

看板Grad-ProbAsk作者 (小YO)時間15年前 (2011/02/06 18:07), 編輯推噓3(3推 0噓 6→)
留言9則, 3人參與, 最新討論串1/1
清大資工97年的11(b) Briefly describe how to use the Knuth-MorrisPratt algorithm to determine if a string is a cyclic rotation of another string in linear time. For example, tea and eat are cyclic rotaions of each other. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.39.4.138
推
02/06 20:03, , 1F
把其中一個複製兩次當Text 另一個當Pattern 用KMP搜尋
02/06 20:03, 1F
→
02/06 20:14, , 2F
F大可以舉例嗎? 謝謝:)
02/06 20:14, 2F
推
02/06 21:39, , 3F
比如說題目裡說的tea跟eat 就把tea複製兩次變成teatea
02/06 21:39, 3F
→
02/06 21:40, , 4F
然後在teatea中找eat =>就在第二個字~第四個字
02/06 21:40, 4F
→
02/06 21:40, , 5F
但我覺得不能隨便找一個複製兩次 應該要找長度長的那個
02/06 21:40, 5F
→
02/06 21:41, , 6F
不然比如說tea 跟 eate , 如果tea複製兩次 會被找到
02/06 21:41, 6F
→
02/06 21:55, , 7F
瞭解了 謝謝:)
02/06 21:55, 7F
推
02/06 23:33, , 8F
如果兩個字串長度不相同 不會是cyclic rotation
02/06 23:33, 8F
→
02/06 23:33, , 9F
我是這樣解讀他的定義的..
02/06 23:33, 9F
‣ 更多 boy5548 的文章
文章代碼(AID): #1DJdBP3Y (Grad-ProbAsk)