Towards a real time algorithm for parameterized longest common prefix computation

Parameterized matching has proven to be an efficient and useful tool for detecting code duplications. This paper presents a technique for calculating parameterized Longest Common Prefix ( p l c p ) in constant time based on the knowledge about the p l c p of the following suffixes. Using this technique, online p-suffix tree construction can be done in worst case time O ( log ⁡ n ) per input symbol. Searching for a pattern of length m in the resulting suffix tree takes O ( min ⁡ { m log ⁡ ( | Σ | + | Π | ), m + log ⁡ n } + m τ Π + t o c c ) time, where t o c c is the number of occurrences of the pattern, and τ Π depends on Π. For constant-sized Π, τ Π = 1, for polynomial-sized Π, τ Π = log ⁡ log ⁡ | Π |, and for unbounded Π, τ Π = log ⁡ | Π |.

Authors

• Amihood Amir
• Eitan Kondratovsky

Keywords

• Online indexing
• Parameterized matching
• Parameterized longest common prefix