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

[neverfly (neverfly)]

假設有兩個字串，已知長度是m，
abcde
accda
這兩個字串的hamming distance是2，
如果一個一個比對，發現不相同的話就+1，
這樣一定會花到m的時間。

請問有可能在constant time做完嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.114.88.169
推 ykjiang:可由減少 linear time 的係數著手
推 ckclark:輸入都不只constant time了
→ neverfly:輸入可以不管，假設已經讀入，也可以做preprocessing
→ neverfly:但字串內容是會變的
推 yoco315:你一個字串最少要「看過一次」，m，你說可能 constant 嗎
推 scan33scan33:請問您的計算model為何？
推 DJWS:1.用猜的(趨近演算法) 2.找m人同時算(平行演算法) 3.m是常數