作者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/cn.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