a**a
发帖数: 4 | 1 0/1字符串长度为n=1000,000,000
1）用什么样的数据结构存储，以便快速搜索(匹配/定位)给定的子串(长度为m=100)，
用n和m表示可能的时间和空间复杂度。
2）设计算法，打印所有出现过两次的子串序列？分析其复杂度。 |
T*****9
发帖数: 2484 | 2 看着像霍夫曼树
可惜我忘记细节了，就是霍夫曼树压缩码那块内容
【在 a**a 的大作中提到】
: 0/1字符串长度为n=1000,000,000
: 1）用什么样的数据结构存储，以便快速搜索(匹配/定位)给定的子串(长度为m=100)，
: 用n和m表示可能的时间和空间复杂度。
: 2）设计算法，打印所有出现过两次的子串序列？分析其复杂度。
|
c*****t
发帖数: 1879 | 3
KMP / BLAST / trie
trie
【在 a**a 的大作中提到】
: 0/1字符串长度为n=1000,000,000
: 1）用什么样的数据结构存储，以便快速搜索(匹配/定位)给定的子串(长度为m=100)，
: 用n和m表示可能的时间和空间复杂度。
: 2）设计算法，打印所有出现过两次的子串序列？分析其复杂度。
|
e*******t
发帖数: 44 | |
e*******t
发帖数: 44 | 5 不对
【在 T*****9 的大作中提到】
: 看着像霍夫曼树
: 可惜我忘记细节了，就是霍夫曼树压缩码那块内容
|
a**a
发帖数: 4 | 6
一般教科书介绍的算法（比如BM,KMP等）是面向普通字符串(任意字符、正常长度、数
组或链串存储)的。
对于超长的二进制串匹配子串的算法，应该能有更高效的存储方式，感觉应该是suffix
tree + Huffman Coding.
【在 e*******t 的大作中提到】
: 这个是经典字符串匹配问题。找本书都有详细答案
|
e*******t
发帖数: 44 | 7 您说得对。我没有注意到。谢谢你指出
suffix
【在 a**a 的大作中提到】
:
: 一般教科书介绍的算法（比如BM,KMP等）是面向普通字符串(任意字符、正常长度、数
: 组或链串存储)的。
: 对于超长的二进制串匹配子串的算法，应该能有更高效的存储方式，感觉应该是suffix
: tree + Huffman Coding.
|
e*******t
发帖数: 44 | 8 这个字符串干嘛要“高效存储方式“？你怎么压缩？
这个题目说二进制串的意思就是不要你用那个最原始的算法，否则扫描的时候回退太麻烦
算法和那个经典问题一样。用基于有限状态机来解决
可以一次转换用多位，而不是只看一位。所以可能有点变化
我的想法
suffix
【在 a**a 的大作中提到】
:
: 一般教科书介绍的算法（比如BM,KMP等）是面向普通字符串(任意字符、正常长度、数
: 组或链串存储)的。
: 对于超长的二进制串匹配子串的算法，应该能有更高效的存储方式，感觉应该是suffix
: tree + Huffman Coding.
|
a**a
发帖数: 4 | 9 要求是匹配算法的时间和空间上的高效，所以要在设计串的存储结构上考虑到：1.尽可
能的少的空间 2.便于快速匹配(可以是任意合适的算法，快就行)
麻烦
【在 e*******t 的大作中提到】
: 这个字符串干嘛要“高效存储方式“？你怎么压缩？
: 这个题目说二进制串的意思就是不要你用那个最原始的算法，否则扫描的时候回退太麻烦
: 算法和那个经典问题一样。用基于有限状态机来解决
: 可以一次转换用多位，而不是只看一位。所以可能有点变化
: 我的想法
:
: suffix
|
e*******t
发帖数: 44 | 10 1 你对所谓算法“空间上高效“理解完全错误
2 压缩解压缩是很废时间的
3 压缩是一个与此完全无关的问题。
4 这个串也就100M的样子
睡觉去了
【在 a**a 的大作中提到】
: 要求是匹配算法的时间和空间上的高效，所以要在设计串的存储结构上考虑到：1.尽可
: 能的少的空间 2.便于快速匹配(可以是任意合适的算法，快就行)
:
: 麻烦
|
a**a
发帖数: 4 | 11 我理解的过程应该是：
子串和母串的数组/链表表示 ---(转换)---> 更优的数据结构 ---(匹配)---> 子串
在母串中定位
题目要求的时间和空间复杂度，是针对“匹配”算法，不是针对 “目标串转换” 的算
法。
考的是使匹配更优所需的串的数据存储结构。
哈夫曼压缩只是一种转换存储的方式，压缩算法的优劣的确和问题无关，关键是压缩所
得的结果是否有利于匹配，当然，这时候的匹配算法很可能必须在转换域（压缩域）中
直接进行（即不需要解压缩），否则的话，是没有意义的。
【在 e*******t 的大作中提到】
: 1 你对所谓算法“空间上高效“理解完全错误
: 2 压缩解压缩是很废时间的
: 3 压缩是一个与此完全无关的问题。
: 4 这个串也就100M的样子
: 睡觉去了
|
D********g
发帖数: 650 | 12 suffix tree
【在 a**a 的大作中提到】
: 0/1字符串长度为n=1000,000,000
: 1）用什么样的数据结构存储，以便快速搜索(匹配/定位)给定的子串(长度为m=100)，
: 用n和m表示可能的时间和空间复杂度。
: 2）设计算法，打印所有出现过两次的子串序列？分析其复杂度。
|
