2026-07-25T09:10:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25961 2026-06-23T13:12:49Z ddc:004 open_access

Efficient Index for Square Pattern Matching Chen, Po-Chun Tsao, Che-Wei Hon, Wing-Kai Köppl, Dominik string algorithms pattern matching indexing squares A string S is called a square if it can be written as the concatenation of two identical strings. Two strings P and Q of the same length are said to square match if, for every substring of P, it is a square if and only if the corresponding substring of Q is also a square. The square pattern matching problem asks for locating all substrings of a given text T of length n that square match a query pattern P of length m. This notion captures similarity in repetition structures and is motivated by applications in areas such as bioinformatics and music structure analysis. In this paper, we introduce a novel technique, called the longest prefix square (LPS) encoding, which represents the square structure of a string as an integer array of the same length. We show that two strings square match if and only if they have identical LPS encodings. Based on this result, we construct an index solving the square pattern matching problem in time O(m lg m + occ) using O(nlg²n) bits of space, where occ denotes the number of occurrences of substrings in T that square match P. If the LPS encoding of P is precomputed, the query time improves to O(m + occ). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Po-Chun Chen and Che-Wei Tsao and Wing-Kai Hon and Dominik Köppl 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.35 urn:nbn:de:0030-drops-259617 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.35 eng https://creativecommons.org/licenses/by/4.0/legalcode