亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

生成給定字符串的所有唯一子字符串

生成給定字符串的所有唯一子字符串

慕少森 2019-10-26 13:38:55
給定一個string s,生成一組所有唯一子字符串的最快方法是什么?示例:因為str = "aba"我們會得到substrs={"a", "b", "ab", "ba", "aba"}。天真的算法是遍歷整個字符串,1..n在每次迭代中生成長度的子字符串,從而產生一個O(n^2)上限。更好的約束可能嗎?(從技術上講這是家庭作業,因此也歡迎只使用指針)
查看完整描述

3 回答

?
犯罪嫌疑人X

TA貢獻2080條經驗 獲得超4個贊

正如其他張貼者所說的,給定字符串可能有O(n ^ 2)個子字符串,因此將它們打印出來的速度不能比這快。但是,存在可以在線性時間內構建的集合的有效表示形式:后綴樹。


查看完整回答
反對 回復 2019-10-26
?
達令說

TA貢獻1821條經驗 獲得超6個贊

這樣做沒有比O(n 2)快的方法,因為一個字符串中總共有O(n 2)個子字符串,因此,如果必須全部生成它們,則它們的數量將是n(n + 1) / 2最壞的情況,因此上下限的為O(n 2) Ω(N 2)。

查看完整回答
反對 回復 2019-10-26
  • 3 回答
  • 0 關注
  • 821 瀏覽

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號