index 原理

image.png

• 5 维窗口，在序列T里面扫过，每走一步，start positon 建立一个index

如何索引？

• 先找索引开始坐标，然后匹配剩下的

  
  

优化

• 3维 index

  
  image.png

• 按照字母大小排序

  
  image.png

• 比如说要查找TGG，用二分法快速定位

  
  image.png

• 最后找到TGG，（大O=log(n)）

  
  image.png