长字符串匹配（BWT编码、后缀数组、倍增算法、FM索引）

用 O(m) 时间复杂度找出一个长度为 m 的短字符串在一个长度为 n 的长字符串中的精确匹配（n>>m），限制长短字符串仅由 A、C、G、T 这四种字符组成。

输入：长短字符串

输出：短字符串在长字符串里的精确匹配

​在匹配前先对长串进行编码和索引计算的预处理，该部分用到BWT编码的思想，并且利用后缀数组和倍增算法对编码过程进行优化。由于长串过长，在编码和存储时对其进行分治处理，并且在索引存储时进行优化，对索引进行间隔存储。在匹配时，用预处理得到的长串编码和索引进行匹配，用到的是FM索引-序列匹配。

BWT编码和索引计算

BWT的全称是The Burrows-Wheeler Transform，也就是所谓的轮转排序。在字符串匹配中首先用BWT对长字符串S进行预处理，得到编码结果BWT(S)和相应索引，用于后续FM索引技术对字符串进行匹配。

BWT编码对应具体步骤如下：

​ 1、设需要编码的长字符串为S，在S末尾加上标记字符 $（该字符的字典序值小于长串中所有字符），得到新字符串S‘，记S’的长度为 len 。

​ 2、对S’进行循环移位，每次将S’中的最后一个字符转移到整个字符串的最前面，一共转移 len 次，每次转移都得到一个长度为 len 的新字符串。

​ 3、把上一步中得到的 len 个新字符串按照字典序排序，得到一个 len × len 的字符矩阵M。

​ 4、M中每个字符串的第一个字符构成 F 列，最后一个字符构成 L 列。L 列即为BWT(S)。