String algorithms and their implementation, intelligent tutors

字符串算法及其实现，智能导师

• 批准号: 25112-2006
• 负责人: Franek, Frantisek
• 金额: $ 1.38万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=390072
• 关键词: String; algorithms; their; implementation; intelligent

(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)

(1)后缀数据结构及相关算法。研究的重点是后缀树和数组的“宽松”版本（即不考虑词典顺序）；它们以高内存效率进行线性时间计算，转换为“常规”后缀树和数组，以及它们在应用程序中的使用。主要目标是一种用于计算后缀树和数组的快速线性非递归内存高效算法。该研究将探索这种算法的以下路径：首先计算数据结构的“宽松”版本，然后将其转换为“常规”结构。 (2) 弦的周期性。研究函数 r(n) 的数学和组合属性 - 所有长度为 n 的字符串的最大运行次数（最大不可扩展重复次数）。主要目标是： 证明渐近 r(n)