parameterized pattern matching (PPM) is the problem of matching between two given parameterized strings over two constant and parameter alphabets. PPM has special applications in software maintenance, information retr...
详细信息
parameterized pattern matching (PPM) is the problem of matching between two given parameterized strings over two constant and parameter alphabets. PPM has special applications in software maintenance, information retrieval, computational biology, and so on. In some applications of PPM, preserving the privacy of the involved parties is essential. For example, a researcher holding an amino acid pattern needs to receive the parameterized matched locations of his/her input with the patterns in a biological database while the database owner has to obtain no information about the matching results and the pattern. In this paper, we define this problem as secure PPM (SPPM), present a scheme to resolve it in the semi-honest and malicious adversarial models, and prove the security of the proposed scheme in the universal composability (UC) framework. The proposed scheme supports wildcard and approximate PPM, too. We evaluate the security and performance of the proposed scheme. The proposed scheme is experimentally evaluated on a case of secure ribonucleic acid (RNA) search over the RNAcentral dataset. Implementation results show that the proposed scheme is secure and efficient for preserving privacy in contexts where PPM is applicable. (C) 2020 Elsevier Inc. All rights reserved.
Let approximate to be a substring consistent equivalence relation (SCER) on strings such that for any two strings x, y, x approximate to y implies that (1) vertical bar x vertical bar = vertical bar y vertical bar and...
详细信息
Let approximate to be a substring consistent equivalence relation (SCER) on strings such that for any two strings x, y, x approximate to y implies that (1) vertical bar x vertical bar = vertical bar y vertical bar and (2) x[i..j] approximate to y[i..j] for all 0 <= i <= j < vertical bar x vertical bar. Examples of SCER are parameterized pattern matching and order-preserving patternmatching. We present a generalized and efficient algorithm for patternmatching with SCER approximate to. Also, we show analogues of Fine and Wilt's periodicity lemma hold for SCER. (C) 2016 Elsevier B.V. All rights reserved.
Given a text and a pattern over two types of symbols called constants and variables, the parameterized pattern matching problem is to find all occurrences of substrings of the text that the pattern matches by substitu...
详细信息
ISBN:
(纸本)9783319731179;9783319731162
Given a text and a pattern over two types of symbols called constants and variables, the parameterized pattern matching problem is to find all occurrences of substrings of the text that the pattern matches by substituting a variable in the text for each variable in the pattern, where the substitution should be injective. The function matching problem is a variant of it that lifts the injection constraint. In this paper, we discuss variants of those problems, where one can substitute a constant or a variable for each variable of the pattern. We give two kinds of algorithms for both problems, a convolution-based method and an extended KMP-based method, and analyze their complexity.
The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array ...
详细信息
The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays. In this paper, we present a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most n, where n is a given threshold. This algorithm runs in O(B-2(n)) time, where B-2(n) is the number of all p-border arrays of length n for a binary parameter alphabet. The problems with a larger alphabet are much more difficult. Still, we present an O(n(1.5)) - time O(n) - space algorithm to verify if a given integer array of length n is a valid p-border array for an unbounded alphabet. The best previously known solution to this task takes time proportional to the n-th Bell number 1/e Sigma(infinity)(k=0) k(n)/k(l), and hence our algorithm is much more efficient. Also, we show that it is possible to enumerate all p-border arrays of length at most n for an unbounded alphabet in O(B(n)n(2.5)) time, where B-n denotes the number of p-border arrays of length n. (C) 2011 Elsevier B.V. All rights reserved.
The problem of the set of k-covers is a distance measure for strings. Another well-studied string comparison measure is that of parameterizedmatching. We consider the problem of the set of parameterized k-covers (k-S...
详细信息
The problem of the set of k-covers is a distance measure for strings. Another well-studied string comparison measure is that of parameterizedmatching. We consider the problem of the set of parameterized k-covers (k-SPC) which combines k-cover measure with parameterizedmatching. We prove that k-SPC is NP-complete. We describe an approach to solve k-SPC. This approach is based on constructing a logical model for k-SPC. (C) 2011 Elsevier B.V. All rights reserved.
The Burrows-Wheeler transform (BWT) provides a succinct way to index text for patternmatching queries. Notable variants are (a) the extended BWT (eBWT) capable to index multiple input texts for circular pattern match...
详细信息
ISBN:
(纸本)9798350385885;9798350385878
The Burrows-Wheeler transform (BWT) provides a succinct way to index text for patternmatching queries. Notable variants are (a) the extended BWT (eBWT) capable to index multiple input texts for circular patternmatching, or (b) the parameterized BWT (pBWT) for parameterized pattern matching. A natural extension is the combination of the virtues of both variants into a new data structure, whose name we coin with extended parameterized BWT (epBWT). We show that the epBWT supports circular patternmatching in context of parameterized pattern matching on multiple texts, within the same complexities as known solutions presented for the pBWT [Kim and Cho, IPL'21] for patterns shorter than the shortest indexed text.
We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterize...
详细信息
ISBN:
(纸本)9783030326852;9783030326869
We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet Sigma and parameterized alphabet Pi, our algorithm runs in O(n pi) time and O(n) words of space, where pi is the number of distinct symbols of Pi in the string.
暂无评论