作者boy5548 (小YO)
看板Grad-ProbAsk
標題[理工] [資結] 97清大資工 Knuth algorithm
時間Sun Feb 6 18:07:18 2011
清大資工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
1F:推 FRAXIS:把其中一個複製兩次當Text 另一個當Pattern 用KMP搜尋 02/06 20:03
2F:→ boy5548:F大可以舉例嗎? 謝謝:) 02/06 20:14
3F:推 jameschou:比如說題目裡說的tea跟eat 就把tea複製兩次變成teatea 02/06 21:39
4F:→ jameschou:然後在teatea中找eat =>就在第二個字~第四個字 02/06 21:40
5F:→ jameschou:但我覺得不能隨便找一個複製兩次 應該要找長度長的那個 02/06 21:40
6F:→ jameschou:不然比如說tea 跟 eate , 如果tea複製兩次 會被找到 02/06 21:41
7F:→ boy5548:瞭解了 謝謝:) 02/06 21:55
8F:推 FRAXIS:如果兩個字串長度不相同 不會是cyclic rotation 02/06 23:33
9F:→ FRAXIS:我是這樣解讀他的定義的.. 02/06 23:33