Abstract
The border and parameterized border (p-border) arrays are data structures used in pattern matching applications for traditional strings from the constant alphabet Σ and parameterized strings (p-strings) from the constant alphabet Σ and the parameter alphabet Π. In this work, we introduce the structural border (s-border) array as defined for an n-length structural string (s-string) T. The s-string is a p-string with the existence of symbol complements in some alphabet Γ. These different alphabets add to both the intricacies and capabilities of pattern matching. Initially, we provide a construction that executes in O(n 2) time to build the s-border array. The paper establishes theory to improve the result to O(n) by proving particular properties of the s-border data structure. This result is significant because of the generalization of the s-string, which is a step beyond the p-string. Using the same construction algorithm, we show how to modify the s-string alphabets to also construct the p-border and the traditional border arrays in linear time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Smyth, W.: Computing Patterns in Strings. Pearson, New York (2003)
Baker, B.: A theory of parameterized pattern matching: Algorithms and applications. In: STOC 1993, pp. 71–80 (1993)
Idury, R., Schäffer, A.: Multiple matching of parameterized patterns. Theor. Comput. Sci. 154, 203–224 (1996)
I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting Parameterized Border Arrays for a Binary Alphabet. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 422–433. Springer, Heidelberg (2009)
I, T., Inenaga, S., Bannai, H., Takeda, M.: Verifying a Parameterized Border Array in O(n 1.5) Time. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 238–250. Springer, Heidelberg (2010)
Baker, B.: Finding clones with dup: Analysis of an experiment. IEEE Trans. Software Eng. 33(9), 608–621 (2007)
Zeidman, B.: Software v. software. IEEE Spectr. 47, 32–53 (2010)
Shibuya, T.: Generalization of a suffix tree for RNA structural pattern matching. Algorithmica 39(1), 1–19 (2004)
Beal, R.: Parameterized Strings: Algorithms and Data Structures. MS Thesis. West Virginia University (2011)
Kosaraju, S.: Faster algorithms for the construction of parameterized suffix trees. In: FOCS 1995, pp. 631-637 (1995)
Cole, R., Hariharan, R.: Faster suffix tree construction with missing suffix links. SIAM J. Comput. 33(1), 26–42 (2003)
Lee, T., Na, J., Park, K.: On-line construction of parameterized suffix trees for large alphabets. Inf. Process. Lett. 111(5), 201–207 (2011)
Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)
Adjeroh, D., Bell, T., Mukherjee, A.: The Burrows-Wheeler Transform: Data Compression, Suffix Arrays and Pattern Matching. Springer, New York (2008)
I, T., Deguchi, S., Bannai, H., Inenaga, S., Takeda, M.: Lightweight Parameterized Suffix Array Construction. In: Fiala, J., Kratochvíl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol. 5874, pp. 312–323. Springer, Heidelberg (2009)
Deguchi, S., Higashijima, F., Bannai, H., Inenaga, S., Takeda, M.: Parameterized suffix arrays for binary strings. In: PSC 2008, pp. 84-94 (2008)
Beal, R., Adjeroh, D.: p-Suffix Sorting as Arithmetic Coding. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2011. LNCS, vol. 7056, pp. 44–56. Springer, Heidelberg (2011)
Beal, R., Adjeroh, D.: p-Suffix Sorting as Arithmetic Coding. JDA 16, 151–169 (2012)
Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Inf. Process. Lett. 49, 111–115 (1994)
Baker, B.: Parameterized pattern matching by Boyer-Moore-type algorithms. In: SODA 1995, pp. 541–550 (1995)
Fredriksson, K., Mozgovoy, M.: Efficient parameterized string matching. Inf. Process. Lett. 100(3), 91–96 (2006)
Beal, R., Adjeroh, D.: Parameterized longest previous factor. Theor. Comput. Sci. 437, 21–34 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beal, R., Adjeroh, D. (2012). Border Array for Structural Strings. In: Arumugam, S., Smyth, W.F. (eds) Combinatorial Algorithms. IWOCA 2012. Lecture Notes in Computer Science, vol 7643. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35926-2_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-35926-2_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35925-5
Online ISBN: 978-3-642-35926-2
eBook Packages: Computer ScienceComputer Science (R0)