1997/10/01 by Brenda S. Baker · 159 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Code (set theory) #Combinatorics #Compressed suffix array #Computer science #Data structure #Identifier #Mathematics #Network Packet Processing and Optimization #Parameterized complexity #Programming language #Set (abstract data type) #String (physics) #Suffix #Suffix tree #Theoretical computer science #Time complexity #Tree (set theory) #Web Data Mining and Analysis
paper · doi:10.1137/s0097539793246707
published in SIAM Journal on Computing 26(5), 1343-1362 (Society for Industrial and Applied Mathematics)
openalex publication_date 1997/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/05
As an aid in software maintenance, it would be useful to be able to track down duplication in large software systems efficiently. Duplication in code is often in the form of sections of code that are the same except for a systematic change of parameters such as identifiers and constants. To model such parameterized duplication in code, this paper introduces the notions of parameterized strings and parameterized matches of parameterized strings. A data structure called a parameterized suffix tree is defined to aid in searching for parameterized matches. For fixed alphabets, algorithms are given to construct a parameterized suffix tree in linear time and to find all maximal parameterized matches over a threshold length in a parameterized p-string in time linear in the size of the input plus the number of matches reported. The algorithms have been implemented, and experimental results show that they perform well on C code.