[数据结构与算法]算法设计：字符串查找数据结构

字符串不一定是一长串地排列在一起，像数组一样，他可能会有数据结构的。现在我们要考虑这个问题。

?

?这个hash表是怎么实现的呢？其实就好比是几个链表，我按照mod3的规矩分成3个，到时候先找链表再找元素（不用数组，用数组空间大）。发现一个问题，其实后三种方法内存是一样大的，hash方法只是搜索速度是链表的几分之一（取决于分几部分），二分查找树才是最快的。

?

数据结构里储存的不再是字符串，而是字符的索引。

这个时候注意力不要放在点上，要放在边上。

?

?

?开头用字母标记一下，假如直接用数字的话那我每次找都要去数组查，开头有个字母就可以判断要不要去查。

?t是叶子的话说明找到头了，直接开比；不是那就看看子节点里开头的字母有没有一样的，有就要注意。开头直接还没P长的直接排除不考虑，有他长的就看看，对这个点使用自己这个函数。

确实，算法一直避免去读数组。

?

?

?这个图就是计录了这个单词的所有可能后缀。

?

?

?