字典里找子串怎么解？generalized suffix tree?# JobHunting - 待字闺中
y*i
1 楼
比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢
string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢
y*i
2 楼
自己顶一下。
KMP不适合多次查询的情况，Aho-Corasick适合查前缀而不是任意位置的子串，所以只
能是suffix tree吧？
KMP不适合多次查询的情况，Aho-Corasick适合查前缀而不是任意位置的子串，所以只
能是suffix tree吧？
r*n
3 楼
为什么KMP不适合呢？KMP只学要预处理一次pattern，然后用生成的dfa去查每个word
s*s
4 楼
应该是用prie。
【在 y*****i 的大作中提到】
: 比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
: string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢
【在 y*****i 的大作中提到】
: 比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
: string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢
l*r
5 楼
prie是什么
【在 s*******s 的大作中提到】
: 应该是用prie。
【在 s*******s 的大作中提到】
: 应该是用prie。
s*s
6 楼
TRIE
http://en.wikipedia.org/wiki/Trie
sorry for the typo
【在 l**********r 的大作中提到】
: prie是什么
http://en.wikipedia.org/wiki/Trie
sorry for the typo
【在 l**********r 的大作中提到】
: prie是什么
y*i
7 楼
Prie是啥？没搜到。对string matching算法很不熟，唉。
【在 s*******s 的大作中提到】
: 应该是用prie。
【在 s*******s 的大作中提到】
: 应该是用prie。
y*i
8 楼
哦。got it。
但是trie能用来搜子串吗？比如wiki上这个例子，ten在这个字典里，现在如果要搜"en
"，trie就不行了吧。
【在 s*******s 的大作中提到】
: TRIE
: http://en.wikipedia.org/wiki/Trie
: sorry for the typo
但是trie能用来搜子串吗？比如wiki上这个例子，ten在这个字典里，现在如果要搜"en
"，trie就不行了吧。
【在 s*******s 的大作中提到】
: TRIE
: http://en.wikipedia.org/wiki/Trie
: sorry for the typo
s*s
9 楼
你说得对，我的想法错了。呵呵
en
【在 y*****i 的大作中提到】
: 哦。got it。
: 但是trie能用来搜子串吗？比如wiki上这个例子，ten在这个字典里，现在如果要搜"en
: "，trie就不行了吧。
en
【在 y*****i 的大作中提到】
: 哦。got it。
: 但是trie能用来搜子串吗？比如wiki上这个例子，ten在这个字典里，现在如果要搜"en
: "，trie就不行了吧。
y*i
10 楼
字典是已知的，pattern是未知的，且多个。这样是不是KMP就不如suffix tree了。每
一个新pattern都得重新搜一次。
就是做题的时候suffix tree感觉比KMP难写多了。。。
【在 r*********n 的大作中提到】
: 为什么KMP不适合呢？KMP只学要预处理一次pattern，然后用生成的dfa去查每个word
一个新pattern都得重新搜一次。
就是做题的时候suffix tree感觉比KMP难写多了。。。
【在 r*********n 的大作中提到】
: 为什么KMP不适合呢？KMP只学要预处理一次pattern，然后用生成的dfa去查每个word
c*p
11 楼
一涉及这个的题，我就彻底无助。。。。
J*3
12 楼
为啥pattern这里是未知的啊？ 不是给定一个string 去字典里挨个找的吗？这个
string不就是pat? 字典的是txt?
【在 y*****i 的大作中提到】
: 字典是已知的，pattern是未知的，且多个。这样是不是KMP就不如suffix tree了。每
: 一个新pattern都得重新搜一次。
: 就是做题的时候suffix tree感觉比KMP难写多了。。。
string不就是pat? 字典的是txt?
【在 y*****i 的大作中提到】
: 字典是已知的，pattern是未知的，且多个。这样是不是KMP就不如suffix tree了。每
: 一个新pattern都得重新搜一次。
: 就是做题的时候suffix tree感觉比KMP难写多了。。。
y*i
13 楼
my bad. 没表述清楚。不是给定一个。是每次给一个。。就像一个真的dict一样。今天
你想查这个词，明天想查那个词，只不过现在我们查的是各种子串们。
【在 J****3 的大作中提到】
: 为啥pattern这里是未知的啊？ 不是给定一个string 去字典里挨个找的吗？这个
: string不就是pat? 字典的是txt?
你想查这个词，明天想查那个词，只不过现在我们查的是各种子串们。
【在 J****3 的大作中提到】
: 为啥pattern这里是未知的啊？ 不是给定一个string 去字典里挨个找的吗？这个
: string不就是pat? 字典的是txt?
g*G
14 楼
如果没理解错的话，应该是trie而不是suffix tree做
trie一般用于这种类似字典的查找，suffix tree一般用来重复查找同一个字符串的子串
【在 y*****i 的大作中提到】
: 比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
: string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢
trie一般用于这种类似字典的查找，suffix tree一般用来重复查找同一个字符串的子串
【在 y*****i 的大作中提到】
: 比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
: string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢
l*0
15 楼
我觉得trie不太行吧？trie是找前缀的，但他这个是要找子串。比如字典里有abcd，
mcd, ncd, 然后要找所有含cd的，那trie岂不是一个都找不出来。可是如果是suffix
tree的话 难道为每一个字典里的string都建一课suffix tree？我觉得可能用那个
rolling hash比较不错。
子串
【在 g**G 的大作中提到】
: 如果没理解错的话，应该是trie而不是suffix tree做
: trie一般用于这种类似字典的查找，suffix tree一般用来重复查找同一个字符串的子串
mcd, ncd, 然后要找所有含cd的，那trie岂不是一个都找不出来。可是如果是suffix
tree的话 难道为每一个字典里的string都建一课suffix tree？我觉得可能用那个
rolling hash比较不错。
子串
【在 g**G 的大作中提到】
: 如果没理解错的话，应该是trie而不是suffix tree做
: trie一般用于这种类似字典的查找，suffix tree一般用来重复查找同一个字符串的子串
r*n
16 楼
那可以把所有词的suffix都放到trie里面去，这样查找速度最快，但是预处理复杂度很
高，不过如果查找次数很多，预处理的overhead平均下来也就不算什么了。
【在 y*****i 的大作中提到】
: my bad. 没表述清楚。不是给定一个。是每次给一个。。就像一个真的dict一样。今天
: 你想查这个词，明天想查那个词，只不过现在我们查的是各种子串们。
高，不过如果查找次数很多，预处理的overhead平均下来也就不算什么了。
【在 y*****i 的大作中提到】
: my bad. 没表述清楚。不是给定一个。是每次给一个。。就像一个真的dict一样。今天
: 你想查这个词，明天想查那个词，只不过现在我们查的是各种子串们。
p*2
17 楼
如果允许preprocess可以做到O（1）
k*j
18 楼
http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/suffixtrees.pdf
PAGE 44
Determine the strings in a database {S1, S2, S3, ..., Sm} that contain
query string q:
Build generalized suffix tree for {S1, S2, S3, ..., Sm}
Follow the path for q in the suffix tree.
Suppose you end at node u: traverse the tree below u, and
output i if you find a string containing #i
PAGE 44
Determine the strings in a database {S1, S2, S3, ..., Sm} that contain
query string q:
Build generalized suffix tree for {S1, S2, S3, ..., Sm}
Follow the path for q in the suffix tree.
Suppose you end at node u: traverse the tree below u, and
output i if you find a string containing #i
f*b
19 楼
赞同！
【在 l*******0 的大作中提到】
: 我觉得trie不太行吧？trie是找前缀的，但他这个是要找子串。比如字典里有abcd，
: mcd, ncd, 然后要找所有含cd的，那trie岂不是一个都找不出来。可是如果是suffix
: tree的话 难道为每一个字典里的string都建一课suffix tree？我觉得可能用那个
: rolling hash比较不错。
:
: 子串
相关阅读
PhD申请Google经验请问H1-B transfer通常需要多少时间求建议，这样的背景能找到什么工作抛砖引玉，讨论一下Jigsaw题？急 求助H1B补充材料问题OPT递交了申请可以改开始日期么有人办过DSP 5 export control license 吗？申请高校H1-B也一定需要LCA吗？google tokyo 怎么样？应聘人口普查员, 考试满分, 却不给我工作, 怎么办?Careercup书第四版一道题的解答有错有人熟悉一个叫Micro-World的公司吗？h1b premium processing 要多久？ (转载)刚刚骗了recruiter!帮选offer：layoff一月，2 offers +1 backgrd check这里有人在citibank工作吗？我想麻烦refer一个职位想问下有人知道如何找下local公司的信息呢？拿到电面，却不知道公司名字送给找工作到绝望边缘的朋友screen interview 是啥意思?在线等