String algorithms and their implementation, intelligent tutors

(1)后缀数据结构及相关算法。研究的重点是后缀树和数组的“宽松”版本(即不考虑词汇法排序)；它们的计算在线性时间内具有很高的存储效率，它们转换成“规则”的后缀树和数组，它们的应用。主要目标是一种计算后缀树和数组的快速线性非递归内存高效算法。这项研究将探索这样一种算法的以下路径：首先计算一个“宽松”版本的数据结构，然后将其转换为“规则”结构。(2)弦的周期性。研究函数r(N)的数学和组合性质。r(N)是所有长度为n的字符串上的最大游程数(最大不可扩展重复次数)。主要目的是：证明r(N)的渐近性。

(1) Suffix data structures and related algorithms. The focus of the research is "relaxed" versions of suffix trees and arrays (i.e. without regards to lexicograhic ordering); their computation in linear time with hight memory efficiency, their transformation to "regular" suffix trees and arrays, their use for applications. The main objective is a fast linear non-recursive memory efficient algorithm for computing suffix trees and arrays. The research will explore the following path to such an algorithm: first compute a "relaxed" version of the data structure, then transform it to the "regular" structure. (2) The periodicity in strings. The investigation of mathematical and combinatorial properties of the function r(n) - the maximun number of runs (maximal non-extendible repetitions) over all strings of length n. The main objectives are: to prove that asymptoticaly r(n)