一个字典字符串查询题目，大牛看看如何解？ - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 一个字典字符串查询题目，大牛看看如何解？

相关主题
● 面试中遇到suffix tree / trie这种题，需要自己实现吗？
● 用trie统计字符串的疑惑
● 字典里找子串怎么解？generalized suffix tree?
● 给字符串，里边是几个单词中间没空格，输出所有可能的句子。
● 这面经题怎么用动态规划做呢？
● 问一个老题，请帮忙解答多谢了
● G家电面经验
● 一道字典题目
● 字典里面如何快速找到一个单词对应的只有一个字母不同的单词
● 求教字典是咋实现的？

相关话题的讨论汇总
话题: 字符串话题: 字典话题: 单词话题: aho话题: corasick

进入JobHunting版参与讨论

1

(共1页)

m*******g 发帖数: 410	1 一个字典 m个单词，平均长度为k，一个非常长的字符串中间没有任何空格，长度为n。设计一个算法找字典中的单词是这个长字符串的子串。条件： 1）只能访问长字符串每个字符一次； 2）n非常长，以至于不能创造长字符串的数据结构。
a*********n 发帖数: 44	2 Aho-Corasick
m*******g 发帖数: 410	3 我的一个思路是：把字典里面单词保存起来，找到字词的最长长度，然后长字符串进行滑窗处理，每个滑窗对所有的单词进行搜索，找到是否有字典中的单词，这貌似不是最优解。
m*******g 发帖数: 410	4 这题如果面试用Aho-Corasick 解，是是不是代码太长了，实际会这么考吗？

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 求教字典是咋实现的？
● amazon ONSITE 面试，求BLESS
● Facebook面经
● G 面试 advanced algorithms
● 来统计下面试时候被问到过的牛逼算法有哪些
● [合集] 微软Phone Internew问题
● 几道微软面试题
● [合集] PayPal@eBay onsite(失败)题目和经验
● 一些面经
● MS onsite 经历

相关话题的讨论汇总
话题: 字符串话题: 字典话题: 单词话题: aho话题: corasick