迅雷校园招聘面试题·····

youzhizhe

实现一个挺高级的字符匹配算法：
例如：“123” 这3个字符，要匹配到：
“1   3  2”     “3（随便一系列的字符）2（随便一系列的字符）1  ”（123的顺序可以打乱）。
求高人的想法。

我说得不好，
其实就是说给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3这些都要找出来
其实就是类似一些和谐系统。。。。。

大家继续讨论。。。。

davelv

就是只要有123这三个字符在的字符串都可以匹配？
那么自然匹配可以在O(n*m)的时间内完成

youzhizhe

求解释··

davelv

求解释··
youzhizhe 发表于 2010-10-15 16:53

自然匹配就是对待匹配的每个字符挨个匹配
设你的待匹配字串长度位n,模式字符串长度位m.
对于待匹配字符串中的任意一个字符最坏情况下要匹配m次，也就是说这个字符不在模式字符串中。
所以最坏情况下总共是m*n此匹配，时间复杂度就是O(m*n)

倘若使用hash表对待字符串进行hash处理O(n)的时间复杂度，那么对于模式字符串中的任意字符，仅需一次hash判断就可以得知是否在待匹配字符串中出现。最坏仅需m次就可以得到结果。时间复杂度为O(m)或者O(n);

spongeliu

hash

cxw06023273

感觉楼主说的太模糊了，我的理解是：查找一系列字符串中含有目的串的问题，即目的串在输入串中的位置不确定。
目的串：
123
输入：
1******3***2 ,12*****3***
结果：匹配
如果是这样的话，感觉bloom filter算法挺适合的，时空效率都可以，呵呵

mcemil

什么乱七八糟的
是求最大匹配？最小匹配？匹配判定？匹配子窜数？

ecjtubaowp

设计hash函数是关键。

newmax123

slip  "123";

测试每个字串都是在b 存在的

是这个意思吧

youzhizhe

我说得不好，
其实就是说给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3这些都要找出来
其实就是类似一些和谐系统