作者joy7658x348 (LAB準時畢業)
看板Grad-ProbAsk
標題[理工] 演算法String_matching
時間Fri Jul 5 11:42:31 2019
大家好:
想請問一個找字串比對的問題
例如:
字串: 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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1562298153.A.D60.html
1F：→ mathtsai: 可以先詳細敘述你的問題嗎 07/05 13:47
2F：推 Aa841018: 以你的例子來說，只要在scan時判斷遇到非B and C時跳過 07/05 14:19
3F：→ Aa841018: 繼續掃，然後除此之外一律+1，累計到1時之後只要沒有出 07/05 14:19
4F：→ Aa841018: 現BC以外的字母，都可算是match，因為含有BC的所有組合 07/05 14:19
5F：→ Aa841018: 都算是目標！ 07/05 14:19
6F：→ Aa841018: 然後碰到BC以外的字母你再重新計算…這樣應該…快一點吧 07/05 14:19
7F：→ Aa841018: ？ 07/05 14:19
我懂A大的意思了!那應該用兩個for迴圈去跑就行了，第一個是A，因為不是B或C
所以仍為false，之後到B判斷是B所以改為true，之後是C仍為true..
這樣複雜度應該是O(mn)就可完成吧! 謝謝回應!
※ 編輯: joy7658x348 (140.123.103.117 臺灣), 07/05/2019 16:43:48