作者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