[理工] 演算法String_matching

看板Grad-ProbAsk作者 (LAB準時畢業)時間6年前 (2019/07/05 11:42), 6年前編輯推噓1(1推 0噓 6→)
留言7則, 2人參與, 6年前最新討論串1/1
大家好: 想請問一個找字串比對的問題 例如: 字串: ABCDCBA 我要找 BC 但同時BC也等於CB 也就是找BC出來的結果不會=1，而是=2 (BC and CB) 我想到的方式是先找BC的全排列，也就是BC跟CB兩種 O(n!) 之後再用KMP去分別找BC跟CB O(m+n) 這樣就會是1+1=2，就能找到2組 請問這樣的想法是不是會比較慢，還是有辦法能夠就一次找出兩種組合? 謝謝大家 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.103.117 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1562298153.A.D60.html
→
07/05 13:47, 6年前 , 1F
可以先詳細敘述你的問題嗎
07/05 13:47, 1F
推
07/05 14:19, 6年前 , 2F
以你的例子來說，只要在scan時判斷遇到非B and C時跳過
07/05 14:19, 2F
→
07/05 14:19, 6年前 , 3F
繼續掃，然後除此之外一律+1，累計到1時之後只要沒有出
07/05 14:19, 3F
→
07/05 14:19, 6年前 , 4F
現BC以外的字母，都可算是match，因為含有BC的所有組合
07/05 14:19, 4F
→
07/05 14:19, 6年前 , 5F
都算是目標！
07/05 14:19, 5F
→
07/05 14:19, 6年前 , 6F
然後碰到BC以外的字母你再重新計算…這樣應該…快一點吧
07/05 14:19, 6F
→
07/05 14:19, 6年前 , 7F
？
07/05 14:19, 7F
我懂A大的意思了!那應該用兩個for迴圈去跑就行了，第一個是A，因為不是B或C 所以仍為false，之後到B判斷是B所以改為true，之後是C仍為true.. 這樣複雜度應該是O(mn)就可完成吧! 謝謝回應! ※ 編輯: joy7658x348 (140.123.103.117 臺灣), 07/05/2019 16:43:48
‣ 更多 joy7658x348 的文章
文章代碼(AID): #1T7iSfrW (Grad-ProbAsk)