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

[boy5548 (小YO)]

清大資工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
推 FRAXIS:把其中一個複製兩次當Text 另一個當Pattern 用KMP搜尋
→ boy5548:F大可以舉例嗎? 謝謝:)
推 jameschou:比如說題目裡說的tea跟eat  就把tea複製兩次變成teatea
→ jameschou:然後在teatea中找eat =>就在第二個字~第四個字
→ jameschou:但我覺得不能隨便找一個複製兩次  應該要找長度長的那個
→ jameschou:不然比如說tea 跟 eate , 如果tea複製兩次 會被找到
→ boy5548:瞭解了 謝謝:)
推 FRAXIS:如果兩個字串長度不相同 不會是cyclic rotation
→ FRAXIS:我是這樣解讀他的定義的..