Search

This paper deals with the Circular Pattern Matching Problem (CPM). In CPM, we are interested in pattern matching between the text $\mathcal T$ and the circular pattern $\mathcal C(\mathcal P)$ of a given pattern $\mathcal P = \mathcal P_1 \ldots \mathcal P_m$. The circular pattern $\mathcal C(\mathcal P)$ is formed by concatenating $\mathcal P_1$ to the right of $\mathcal P_m$. We can view $\mathcal C(\mathcal P)$ as a set of m patterns starting at positions j ∈ [1..m] and wrapping around the end and if any of these patterns matches $\mathcal T$, we find a match for $\mathcal C(\mathcal P)$. In this paper, we present two efficient data structures to index circular patterns. This problem has applications in pattern matching in geometric and astronomical data as well as in computer graphics and bioinformatics. [ABSTRACT FROM AUTHOR]

In this paper, we present a new and efficient algorithm for solving the LCS problem for two strings. Our algorithm runs in $O(\mathcal R\log\log n + n)$ time, where $\mathcal R$ is the total number of ordered pairs of positions at which the two strings match. [ABSTRACT FROM AUTHOR]

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both cases, we develop solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the classic and well-studied longest common subsequence (LCS) problem and study some new variants, first introduced and studied by Rahman and Iliopoulos [Algorithms for Computing Variants of the Longest Common Subsequence Problem, ISAAC 2006]. Here we define a generalization of these variants, the longest parameterized common subsequence (LPCS) problem, and show how to solve it in O(n2) and time. Furthermore, we show how to compute two variants of LCS, RELAG and RIFIG in time. [ABSTRACT FROM AUTHOR]

In this paper we have presented new algorithms to handle the pattern matching problem where the pattern can contain variable length gaps. Given a pattern P with variable length gaps and a text T our algorithm works in O(n + m + α log(max1<=i<=l(bi-ai))) time where n is the length of the text, m is the summation of the lengths of the component subpatterns, α is the total number of occurrences of the component subpatterns in the text and ai and bi are, respectively, the minimum and maximum number of don't cares allowed between the ith and (i+1)st component of the pattern. We also present another algorithm which, given a suffix array of the text, can report whether P occurs in T in O(m + α loglogn) time. Both the algorithms record information to report all the occurrences of P in T. Furthermore, the techniques used in our algorithms are shown to be useful in many other contexts. [ABSTRACT FROM AUTHOR]

We define an agent to be any node in the network that is prepared to provide some services to other parties when requested. Such services may be required for various purposes and then, searching and establishing communication with the agent will be necessary. The agent search may be oriented along a particular direction to reduce network load and optimize overall performance. Such oriented algorithms already exist. In this paper we have given a communications protocol that may use such oriented algorithm, defined its request and response packet formats and shown the simulation results for overhead incurred in such communication. [ABSTRACT FROM AUTHOR]

In this paper, we present a finite automata based algorithm for solving the constrainedlongestcommonsubsequence problem for degeneratestrings. A string is a sequence of symbols from a given alphabet Σ. A subsequenceu of a string x is obtained by deleting some characters from u (not necessarily contiguous). Given two strings x and y, u is a commonsubsequence of x and y, if u is a subsequence of both x and y. And, u is a longestcommonsubsequence (LCS) of x and y, if it is the longest among all such subsequences. Given two strings x and y, the LCS problem aims to compute a longest common subsequence of them. We study a newer variant of the classic LCS problem, namely the Constrained LCS problem (CLCS). In CLCS, the computed longest common subsequence must also be a supersequence of a third given string, say z [3,2,1]. [ABSTRACT FROM AUTHOR]