Author name cluster

Eitan Kondratovsky

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2024 Journal Article

On suffix tree detection

Amihood Amir
Eitan Kondratovsky
Avivit Levy

A suffix tree is a fundamental data structure for string processing and information retrieval, however, its structure is still not well understood. The suffix trees reverse engineering problem, which its research aims at reducing this gap, is the following. Given an ordered rooted tree T with unlabeled edges, determine whether there exists a string w such that the unlabeled-edges suffix tree of w is isomorphic to T. Previous studies on this problem consider the relaxation of having the suffix links as well as assume a binary alphabet. This paper is the first to consider the suffix tree detection problem, in which the relaxation of having suffix links as input is removed. We study suffix tree detection on two scenarios that are interesting per se. We provide a suffix tree detection algorithm for general alphabet periodic strings. Given an ordered tree T with n leaves, our detection algorithm takes O ( n + | Σ | p ) -time, where p is the unknown in advance length of a period that repeats at least 3 times in a string S having a suffix tree structure identical to T, if such S exists. Therefore, it is a polynomial time algorithm if p is a constant and a linear time algorithm if, in addition, the alphabet has a sub-linear size. We also show some necessary (but insufficient) conditions for binary alphabet general strings suffix tree detection. By this we take another step towards understanding suffix trees structure.

Details DOI

TCS Journal 2024 Journal Article

Reconstructing parameterized strings from parameterized suffix and LCP arrays

Amihood Amir
Eitan Kondratovsky
Gad M. Landau
Shoshana Marcus
Dina Sokol

Reconstructing input from a data structure entails determining whether an instance of the data structure is in fact valid or not, and if valid, discovering the underlying data that it represents. In this paper we consider the parameterized suffix array (pSA) along with its corresponding parameterized longest-common-prefix (pLCP) array and solve the following problem. Given two arrays of numbers as input, A and P, does there exist a parameterized string S such that A is its pSA and P is its pLCP array? If the answer is positive, our algorithm produces a string S whose pSA is A and whose pLCP array is P. Although the naive approach would have to consider an exponential number of possibilities for such a string S, our algorithm's time complexity is only O ( n 2 ) for input arrays of size n.

Details DOI

TCS Journal 2021 Journal Article

Towards a real time algorithm for parameterized longest common prefix computation

Amihood Amir
Eitan Kondratovsky

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 ⁡ | Π |.

Details DOI