n*******r
发帖数: 12 | 1 关于suffix tree的
suppose suffix trees are available for text files T1 and T2. Given that
you wish to efficiently determine if a given pattern p appears in the
concatenation T1T2 of the two text files, how would you proceed.
简单的说，就是有文件T1和T2（纯文本文件）的suffix tree，想查找一个长度n的字符
串p是不是出
现在T1T2中。请给出有效的算法。 |
n*******r
发帖数: 12 | 2 比如T1：abdfjaosdjfaodfjafd
比如T2：asdjfajdfiadadfkdkf
p:afdasdj
p的afd在T1，跟着asdj在T2。
现在能想到的就是brute force，for (i=1 to n), 把p截两段，然后分别在T1,T2中查
找。不过这样复杂度至少O（n3）.感觉上应该有更简单的发法，还请各位大侠指教啊～ |
X****r
发帖数: 3557 | 3 你的O(n^3)怎么来的？匹配某个字符串是否为前缀或后缀只要O(n)啊，循环一次也就只是
O(n^2)而已？
【在 n*******r 的大作中提到】
: 比如T1：abdfjaosdjfaodfjafd
: 比如T2：asdjfajdfiadadfkdkf
: p:afdasdj
: p的afd在T1，跟着asdj在T2。
: 现在能想到的就是brute force，for (i=1 to n), 把p截两段，然后分别在T1,T2中查
: 找。不过这样复杂度至少O（n3）.感觉上应该有更简单的发法，还请各位大侠指教啊～
|
X****r
发帖数: 3557 | 4 先检查p在不在T1中，再检查p在不在T2中，然后取T1的后n个字符和T2的前n个字符组成
一个
字符串Tc，检查p在不在Tc中。以上皆为O(n)，所以最后也是O(n)。
【在 n*******r 的大作中提到】
: 关于suffix tree的
: suppose suffix trees are available for text files T1 and T2. Given that
: you wish to efficiently determine if a given pattern p appears in the
: concatenation T1T2 of the two text files, how would you proceed.
: 简单的说，就是有文件T1和T2（纯文本文件）的suffix tree，想查找一个长度n的字符
: 串p是不是出
: 现在T1T2中。请给出有效的算法。
|
n*******r
发帖数: 12 | |
