算法 php 字典匹配

[whatisnew]

看到一哥们发的面试题，我突然想起来，刚毕业那会找工作有人问过我这个一个问题：

现有10+位数(9,999,999,999)的关键字组成的一个词典

用户输入(n)个字数，要求使用纯 php(不可以使用php内置函数，不可以使用c语言扩展) 逐字匹配，词典内的关键字，效率应低于30毫秒以内。

然后，我想了很久，就说只能把常见关键词做一个热度顺序，用贝叶斯方法去实现，但是效率。。。

然后，我就问正确的方法是什么啊，然后，被鄙视了一番，然后也没有告诉我正确的方法，然后就被 pass了

后来lz成了c/cpp程序员，然后这么多年过去了，我到现在也没明白这个问题用纯 php 应该怎么解决
哈哈哈

[omengye]

单词查找树?

[whatisnew]

@omengye 当时一下子紧张的不得了，尼玛刚毕业就问我这么高深的问题，我在脑海里先把他的要求过了一遍，然后，突然想到贝叶斯的算法(其实很多垃圾邮件的过滤算法也是基于贝叶斯)，就抛出来了这么一句。其实被鄙视完了之后，我本来要求实习工资5k的，他说我基础差3k就很高了，然后，我就说这个大家都是5k，然后就被拒绝了，后来楼主去了当时最火的一个游戏公司做了 c/cpp 程序员，工资5k，哈哈哈

[b821025551b]

foreach ($array as $k => $v){
if($v==='xxx'){
result[$k] = $v;
}
return result;

[whatisnew]

@b821025551b 亲。。。你这个明显不行啊

我举个例子，用户输入10位数的中文字，字典里有10位数的中文字，复杂程度是 O(n) 的99999999/2*999999999倍，这样的话 foreach 是找死啊

[messyidea]

我想到了ac自动机

[omengye]

@whatisnew 哈哈 楼主当年运气不错。现在找工作啥的先看算法好不好，不好就没个好印象了，其他问题也懒得问。。。

[whatisnew]

@omengye 其实工作这么多年，我也问过几个高级php工程师，他们都说不太可能的。我估计当时面试的人就是为了压低的的实习工资。。。

[b821025551b]

@whatisnew 如果是我去做那个面试，我就会这么回答；这道题考的不是算法，而是情商。

[omengye]

@whatisnew 汗。。。

[shiny]

记得有人用 trie 树来做过，不过是扩展，不知道纯 PHP 效果如何。

[laoyuan]

php 又没有词典，这些关键字是保存在文本文件里么？怎么也得几十G，内存装不下啊

[laoyuan]

就算关键字数据总共100G，对关键字取MD5，存3层文件夹，每层256个，总共256^3 个文件，每个文件就不到6K了，目标关键字取MD5，直接定位文件，肯定30毫秒以内

[zhangcc]

我觉得问这样的问题就是脑残，如果能用php内置函数或者c扩展来写算法(能试算法更优)，那谁几把实际开发中用纯php啊

[whahuzhihao]

匹配 是指判断字典里有没有这个数字吗？
如果是的话，用trie树呀，10位数字而已

[whatisnew]

@whahuzhihao 亲 是任意长度的字符串