l****i
发帖数: 396 | 1 还是可以假设有这么一个数据结构ready？
有经验的大牛们介绍一下经验？谢谢~ |
b*****u
发帖数: 648 | |
i***h
发帖数: 12655 | 3 这个初始化不算难写吧
貌似Cracking the Coding Interview 有？ |
Z**********4
发帖数: 528 | |
S******t
发帖数: 151 | 5 Trie是好写的，面试题如果需要用suffix tree我认为就可以假定要不是面试者题目理
解错了要不就是算法想错了……
【在 l****i 的大作中提到】
: 还是可以假设有这么一个数据结构ready？
: 有经验的大牛们介绍一下经验？谢谢~
|
l****i
发帖数: 396 | 6 书上吗？好像不是最优的？
【在 i***h 的大作中提到】
: 这个初始化不算难写吧
: 貌似Cracking the Coding Interview 有？
|
r**h
发帖数: 1288 | |
l****i
发帖数: 396 | 8 比如cc150 18.8这题
string s and a array of smaller T, search s for each small stirng in T
【在 S******t 的大作中提到】
: Trie是好写的，面试题如果需要用suffix tree我认为就可以假定要不是面试者题目理
: 解错了要不就是算法想错了……
|
i***h
发帖数: 12655 | 9 有个应急办法是suffix array
不是最优，但是好写多了，ＳＴＬ很快搞定 |
w********p
发帖数: 948 | 10 我电面就被考到了。
写两遍就没啥难度了。认真的。 比那个二维水滴水库容易太多了。
【在 l****i 的大作中提到】
: 还是可以假设有这么一个数据结构ready？
: 有经验的大牛们介绍一下经验？谢谢~
|
|
|
l****i
发帖数: 396 | 11 trie 还是 suffix tree？
suffix tree是写最优的那个吗？
【在 w********p 的大作中提到】
: 我电面就被考到了。
: 写两遍就没啥难度了。认真的。 比那个二维水滴水库容易太多了。
|
i***h
发帖数: 12655 | 12 电面上 suffix tree 比较邪恶
【在 w********p 的大作中提到】
: 我电面就被考到了。
: 写两遍就没啥难度了。认真的。 比那个二维水滴水库容易太多了。
|
x*****0
发帖数: 452 | |
S******t
发帖数: 151 | 14 我对于这个问题的理解是最好用Aho-Corasick Algorithm而不是用Suffix Tree，Aho-
Corasick就是做多串匹配用的，实现复杂度也低很多。
http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matchi
Suffix Tree的线性构造算法是非常复杂的，我的印象里面要在300行以上(以Ukkonen算
法为例)，而非线性的构造算法则毫无意义，还不如直接brute force的去匹配(比如说
CC150上的算法)。
Suffix Array的实现稍微简单一些，但是Linear Time的构造算法仍然并不好理解，我
的印象里三分法的实现复杂度应该在30-50行，而且几乎是千篇一律的模板，倍增法的
实现虽然好写一些但是复杂度就不是O(n)而是O(nlogn)的，不知道最近是不是有更好的
实现方式了，还请各位不吝指教。。。
【在 l****i 的大作中提到】
: 比如cc150 18.8这题
: string s and a array of smaller T, search s for each small stirng in T
|
A*****i
发帖数: 3587 | |
S******t
发帖数: 151 | 16 AC compact一点的话50多行吧
【在 A*****i 的大作中提到】
: AC自动机也得写将近100行，不信可以试试
|
r*******e
发帖数: 7583 | 17 对于mutiple pattern search
另一种容易实现的是Rabin-Karp
http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
思路非常简单，在brute force基础上构造一个rolling hash
复杂度O(n+k)
【在 S******t 的大作中提到】
: 我对于这个问题的理解是最好用Aho-Corasick Algorithm而不是用Suffix Tree，Aho-
: Corasick就是做多串匹配用的，实现复杂度也低很多。
: http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matchi
: Suffix Tree的线性构造算法是非常复杂的，我的印象里面要在300行以上(以Ukkonen算
: 法为例)，而非线性的构造算法则毫无意义，还不如直接brute force的去匹配(比如说
: CC150上的算法)。
: Suffix Array的实现稍微简单一些，但是Linear Time的构造算法仍然并不好理解，我
: 的印象里三分法的实现复杂度应该在30-50行，而且几乎是千篇一律的模板，倍增法的
: 实现虽然好写一些但是复杂度就不是O(n)而是O(nlogn)的，不知道最近是不是有更好的
: 实现方式了，还请各位不吝指教。。。
|
S******t
发帖数: 151 | 18 +1
这个的实现复杂度秒杀一众AC自动机, 后缀xxx :)
【在 r*******e 的大作中提到】
: 对于mutiple pattern search
: 另一种容易实现的是Rabin-Karp
: http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
: 思路非常简单，在brute force基础上构造一个rolling hash
: 复杂度O(n+k)
|
