谷歌店面.. 跪

huntersjm 发表于 2019-4-10 11:27
Lz搜一下 ac自动机 ，初始化构建好后可以做到 O(1) 复杂度的判断是否match

O(1) 不行吧,有了input:aaabbbccc 输入了个新的 至少要往前拿substring 这就不是constant time了

迷彩的瓜皮帽 发表于 2019-4-16 10:40
O(1) 不行吧,有了input:aaabbbccc 输入了个新的 至少要往前拿substring 这就不是constant time了

不需要的，你看一下这个算法，如果回溯前面的字符串就不需要用这个算法了

迷彩的瓜皮帽 发表于 2019-4-16 10:40
O(1) 不行吧,有了input:aaabbbccc 输入了个新的 至少要往前拿substring 这就不是constant time了

你可以理解成状态机，根据当前的输入走到下一个状态，这个状态就包含了匹配的字符串信息

多谢楼主分享！

kaipeng21 发表于 2019-4-11 00:36
这个，电面写得出来吗。。。

太复杂了，看跪了
店面够时间写吗？

建议暴力解。。。
参考例子比如

dict = ["abc", "abcde"]
input = abcde

的时候

G家店面 就上kmp  感觉是道劝退题