[理工] 演算法String_matching

[joy7658x348 (LAB準時畢業)]

大家好:

想請問一個找字串比對的問題

例如:

字串: 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
→ mathtsai: 可以先詳細敘述你的問題嗎
推 Aa841018: 以你的例子來說，只要在scan時判斷遇到非B and C時跳過
→ Aa841018: 繼續掃，然後除此之外一律+1，累計到1時之後只要沒有出
→ Aa841018: 現BC以外的字母，都可算是match，因為含有BC的所有組合
→ Aa841018: 都算是目標！
→ Aa841018: 然後碰到BC以外的字母你再重新計算…這樣應該…快一點吧
→ Aa841018: ？
我懂A大的意思了!那應該用兩個for迴圈去跑就行了，第一個是A，因為不是B或C
所以仍為false，之後到B判斷是B所以改為true，之後是C仍為true..
這樣複雜度應該是O(mn)就可完成吧! 謝謝回應!
※ 編輯: joy7658x348 (140.123.103.117 臺灣), 07/05/2019 16:43:48