无顺序约束的字符串匹配问题
字符串A较长，字符串B较短，如何以最短时间判断出B里的所有字母在A中都有: ？B?A
举例：
A=abcdeabcdft，B=dcea，返回ture
若：B=dfgz，返回false
本题没有字符串顺序约束，不需要保证B中字母在A出现的相对顺序不变。下文帮助大家如何一步步优化匹配算法。（有顺序约束的字符串匹配问题，请大家参考KMP算法）
设len(A)=m,len(B)=n
- 最简单的方法-轮询O(m ? n)
轮询字符串B中的每个字母，看其是否在A中出现过。即判断 ？Bi∈A 。这种方法是最笨的方法，时间复杂度为O(m ? n)，不可取。
- 先排序，再同时轮询两个字符串O( mlogm )
可以先对两个字符串按字典排序，然后在A中找到和B相同的起始位置，同时进行轮询。此时时间复杂度分类两段：
排序：O(n logn +m logm )（一般排序）
轮询：O(m+n)
整体是 mlogm 的时间复杂度，如果排序使用O(m)的方法就另说。
文章图片
- 使用hashtable: O( α m+ β n)
【无顺序约束的字符串匹配问题】hashtable的优点是查询时间为O(1)，故我们可以轮询字符串A，将其放在hashtable里O(m)，然后轮询字符串B，在hashtable里查询每个字母 Bi ，看能否找到O(n)。这样时间复杂度为O(m+n)，这是典型以空间换时间的做法。不过举一个不太恰当的例子，若在hashtable里字母a，b，c有相同的索引值，查询时间就不是O(1)了，得加上key值比较的时间。说到这，大家是不是得去看看hashtable的工作原理啦。
文章图片
- 利用素数-O(m+n)
对于26个英文字母，给予每个字母分配一个素数，从2开始，往后类推。a:2, b:3, c:5, d:7?
这样，轮询字符串A，将每个字母代表的素数相乘，这样会得到一个较大的数Big。然后轮询字符串B，若其字母代表的素数能被Big整除，就表示 Bi?A ，若有余数返回false。即使字符串A中有重复字母，仍然可以在O(m+n)时间复杂度内求得结果。
推荐阅读
- 学无止境，人生还很长
- jhipster|jhipster 升级无效问题
- 说的真好
- 解决SpringBoot引用别的模块无法注入的问题
- 抱着梦的无眠
- 松软可口易消化，无需烤箱超简单，新手麻麻也能轻松成功~
- 公园游
- 2018-07-27读书心得
- 今天“大暑”！“赤日几时过，清风无处寻！”
- 无故.