RT Book, Section
T1 Average-case analysis of pattern-matching in trees under the BST probability model
A1 Sánchez Couso, José Ramón
A1 Fernández Camacho, María Inés
A2 Abiteboul, Serge
A2 Shamir, Eli
AB We analyze the average behaviour under the bst probability model of the simplest and most commonly used sequential tree-matching algorithm. When the uniform probability model for the input is assumed, it is well known that it takes O(n) steps on average to search all occurrences of a random pattern P in a random text T of joint size n. Under the bst probability model the analysis is itself more complex, involving the solution of partial differential equations. Nevertheless the difficulty to solve one of partial differential equations concerned leads us to seek for analytic properties of that solution which allow us to conclude, without the explicit knowledge of that solution, the main result: searching for all occurrences of a random pattern in a random binary tree of joint size n and distributed accordingly to the bst probability model is O(n ln n) on the average.
PB Springer
SN 978-3-540-58201-4
YR 1994
FD 1994
LK https://hdl.handle.net/20.500.14352/60652
UL https://hdl.handle.net/20.500.14352/60652
NO 21st International Colloquium, ICALP 94 Jerusalem, Israel, July 11–14, 1994 Proceedings
DS Docta Complutense
RD 17 abr 2025