线性时间创建suffix tree

在复习string算法的时候容易遇到需要用suffix tree处理的题目，但是一直对如何创建suffix tree不是很清楚，看似很复杂的样子就不想继续深入看了。最近因为时间比较多，好不容易静心看了看一个牛逼的算法而且也不算太复杂难懂，在面试的时候虽然很难能写完整代码，但是至少能够写伪码。
数据结构
childern 是一个256位的node数组，start是连接这个节点的边start的index，end是结尾的index，因为所有的叶子节点的end会根据输入pos一直变化都string parse完毕，所以每个叶子的节点的end需要是一个存int的object。
全局变量

remainingSuffixCount 表示还需要处理的suffix，每次开始遍历一个字母的时候都需要把这个数加一，在处理完毕之后需要减1，不是每次遍历都需要处理，

activeEdge 也是 如果不需要回溯，activeEdge = 当前pos 否则 pos - remainingSuffixCount + 1

public class NSInteger{

    int value;

    public NSInteger(int i){

    value = i;

    }

}

public class Node{

   Node[] children;

   Node suffixLink;

   int start;

   NSInteger end;

   int suffixIndex;

}

遍历是从头开始的，而不是从最后一个，每次遍历的原则是如果这个字母是从root开始没有出现过，是一个新的字母就创建一个新的leaf node，例如abcabxabcd
前面三个遍历完的情况如下，下面遍历第四个字母a和第五个字母b，因为从root开始遍历