作者neverfly (neverfly)
站內Prob_Solve
標題[請益] 計算兩字串間hamming distance的最短時間
時間Thu Aug 21 12:26:04 2008
假設有兩個字串，已知長度是m，
abcde
accda
這兩個字串的hamming distance是2，
如果一個一個比對，發現不相同的話就+1，
這樣一定會花到m的時間。
請問有可能在constant time做完嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.88.169
1F：推 ykjiang:可由減少 linear time 的係數著手 08/21 12:37
2F：推 ckclark:輸入都不只constant time了 08/21 12:39
3F：→ neverfly:輸入可以不管，假設已經讀入，也可以做preprocessing 08/21 18:15
4F：→ neverfly:但字串內容是會變的 08/21 18:15
5F：推 yoco315:你一個字串最少要「看過一次」，m，你說可能 constant 嗎 08/23 14:43
6F：推 scan33scan33:請問您的計算model為何？ 08/26 01:45
7F：推 DJWS:1.用猜的(趨近演算法) 2.找m人同時算(平行演算法) 3.m是常數 08/26 10:11