[請益] 計算兩字串間hamming distance的最短時間

看板Prob_Solve作者 (neverfly)時間15年前 (2008/08/21 12:26), 編輯推噓5(5推 0噓 2→)
留言7則, 6人參與, 最新討論串1/1
假設有兩個字串，已知長度是m， abcde accda 這兩個字串的hamming distance是2， 如果一個一個比對，發現不相同的話就+1， 這樣一定會花到m的時間。 請問有可能在constant time做完嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.88.169
推
08/21 12:37, , 1F
可由減少 linear time 的係數著手
08/21 12:37, 1F
推
08/21 12:39, , 2F
輸入都不只constant time了
08/21 12:39, 2F
→
08/21 18:15, , 3F
輸入可以不管，假設已經讀入，也可以做preprocessing
08/21 18:15, 3F
→
08/21 18:15, , 4F
但字串內容是會變的
08/21 18:15, 4F
推
08/23 14:43, , 5F
你一個字串最少要「看過一次」，m，你說可能 constant 嗎
08/23 14:43, 5F
推
08/26 01:45, , 6F
請問您的計算model為何？
08/26 01:45, 6F
推
08/26 10:11, , 7F
1.用猜的(趨近演算法) 2.找m人同時算(平行演算法) 3.m是常數
08/26 10:11, 7F
‣ 更多 neverfly 的文章
文章代碼(AID): #18hEvT8Q (Prob_Solve)