Range LCP
作者：
Highlights：
• The paper defines the Range LCP problem – a generalization of the LCP problem.
• The input of the problem is a range of indices in a preprocessed n-length string.
• The output is the pair of indices in the input range having the maximum LCP.
• The new concept of bridges and optimal bridges in a string is defined and used.
• After O(nlog2n) time processing, queries can be answered in O(loglogn) time.
摘要
•The paper defines the Range LCP problem – a generalization of the LCP problem.•The input of the problem is a range of indices in a preprocessed n-length string.•The output is the pair of indices in the input range having the maximum LCP.•The new concept of bridges and optimal bridges in a string is defined and used.•After O(nlog2n) time processing, queries can be answered in O(loglogn) time.
论文关键词：Data structures,LCP,Pattern matching
论文评审过程：Received 29 January 2013, Revised 21 January 2014, Accepted 5 February 2014, Available online 14 February 2014.
论文官网地址：https://doi.org/10.1016/j.jcss.2014.02.010
