从昨天早晨捉到今天中午…… 终于捉出来了…… 太蛋疼了TAT
做的这道题目 http://acm.fzu.edu.cn/problem.php?pid=1916
题目主要考点就是要求你维护一个字符串，支持往末尾插入一个字符和查询有多少个不同的字串。
这个往末尾插入字符和后缀树Ukkonen的做法很相似。考虑假设我们已经得到了字符串S的后缀树，我们要计算往最后插入一个字符能得到的新不同子串数目。显然原来后缀树中的叶结点都能变成不同的字串，而插入新字符而新建立的叶结点也是不同字串。于是新得到的不同子串数目就是后缀树的叶结点数目。于是就直接Ukkonen了……
话说真心感谢ZT的帮助，给了我一堆参考资料和他的后缀树模板，真心谢谢…… 昨天看了一天终于看懂了orz
代码 http://ideone.com/LpjSx