PTT數位生活區 / C_and_CPP (C/C++)

[問題] 從多個長序列中找到最符合短序列的演算法

看板C_and_CPP (C/C++)作者 (demisoda)時間15年前 (2011/03/08 16:41), 編輯推噓1(1推 0噓 9→)
留言10則, 3人參與, 最新討論串1/1
說得更詳細一點 就是有約10個長序列, 1個短序列 想要從10個長序列中找出一個 (長序列的子序列和短序列很相似的) 如 L1:ABCDEFFFFGFFFFC L2:ZXCRTDFFFJCFFPX L3:AUFJKELJHKFKJWW S: FFFFFFF 乍看之下S應該是和L1的子序列比較相似 想請問有沒有類似的演算法或關鍵字 目前想到的就是一般的字串批配演算法+edit distance暴力法...感覺很差... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.215.216
→
03/08 17:05, , 1F
你需要題目練習嗎？ ACM UVa 164。
03/08 17:05, 1F
→
03/08 17:06, , 2F
我是AC了，但很久以前，備份太多不曉得在那了。
03/08 17:06, 2F
→
03/08 17:07, , 3F
回想起好像DP可解，但又有點不確定，太久了。
03/08 17:07, 3F
推
03/08 17:08, , 4F
longest common subsequence, Dynamic programming
03/08 17:08, 4F
→
03/08 17:20, , 5F
樓上的LCS部分case會對，部分case會ambiguous。
03/08 17:20, 5F
→
03/08 17:21, , 6F
字串1：AFFFB，字串2：CFFF，尋找字串FFF。
03/08 17:21, 6F
→
03/08 17:22, , 7F
LCS跑出應該都是3，但是字串2只要消去1字元，較相似。
03/08 17:22, 7F
→
03/08 17:32, , 8F
原po也許該定義相似的規則，在新增，刪除，修改的權重。
03/08 17:32, 8F
→
03/08 17:33, , 9F
如果三個方式的權重都一樣，CFF和AFFF找FFF會是等價的。
03/08 17:33, 9F
→
03/09 10:38, , 10F
找一下local alignment的演算法吧~
03/09 10:38, 10F
‣ 更多 demisoda 的文章
文章代碼(AID): #1DTUku4y (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 demisoda 的文章
文章代碼(AID): #1DTUku4y (C_and_CPP)