This paper presents a general technique for optimally transforming any dynamic data structure that operates on atomic and indivisible keys by constant-time comparisons, into a data structure that handles unbounded-length keys whose comparison cost is not a constant. Examples of these keys are strings, multidimensional points, multiple-precision numbers, multikey data (e.g., records), XML paths, URL addresses, etc. The technique is more general than what has been done in previous work as no particular exploitation of the underlying structure is required. The only requirement is that the insertion of a key must identify its predecessor or its successor. Using the proposed technique, online suffix tree construction can be done in worst case time $O(\log n)$ per input symbol (as opposed to amortized $O(\log n)$ time per symbol, achieved by previously known algorithms). To our knowledge, our algorithm is the first that achieves $O(\log n)$ worst case time per input symbol. Searching for a pattern of length $m$ in the resulting suffix tree takes $O(\min(m \log |\Sigma|, m + \log n) + tocc)$ time, where $tocc$ is the number of occurrences of the pattern. The paper also describes more applications and shows how to obtain alternative methods for dealing with suffix sorting, dynamic lowest common ancestors, and order maintenance. The technical features of the proposed technique for a given data structure $\mathscr{D}$ are the following ones. The new data structure $\mathscr{D}'$ is obtained from $\mathscr{D}$ by augmenting the latter with an oracle for strings, extending the functionalities of the Dietz--Sleator list for order maintenance [P. F. Dietz and D. D. Sleator, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 365--372; A. Tsakalidis, Acta Inform., 21 (1984), pp. 101--112]. The space complexity of $\mathscr{D}'$ is $\mathscr{S}(n) + O(n)$ memory cells for storing $n$ keys, where $\mathscr{S}(n)$ denotes the space complexity of $\mathscr{D}$. Then, each operation involving $O(1)$ keys taken from $\mathscr{D}'$ requires $O(\mathscr{T}(n))$ time, where $\mathscr{T}(n)$ denotes the time complexity of the corresponding operation originally supported in $\mathscr{D}$. Each operation involving a key $y$ not stored in $\mathscr{D}'$ takes $O(\mathscr{T}(n) + |y|)$ time, where $|y|$ denotes the length of $y$. For the special case where the oracle handles suffixes of a string, the achieved insertion time is $O(\mathscr{T}(n))$.

We consider a class of pattern matching problems where a normalizing polynomial transformation can be applied at every alignment of the pattern and text. Normalized pattern matching plays a key role in fields as diverse as image processing and musical information processing, where application specific transformations are often applied to the input. By considering a wide range of such transformations, we provide fast algorithms and the first lower bounds for both new and old problems. Given a pattern of length $m$ and a longer text of length $n$, where both are assumed to contain integer values only, we first show $O(n\log m)$ time algorithms for pattern matching under linear transformations even when wildcard symbols can occur in the input. We then show how to extend the technique to polynomial transformations of arbitrary degree. Next we consider the problem of finding the minimum Hamming distance under polynomial transformation. We show that, for any $\varepsilon>0$, there cannot exist an $O(nm^{1-\varepsilon})$ time algorithm for additive and linear transformations conditional on the hardness of the classic 3Sum problem. Finally, we consider a version of the Hamming distance problem under additive transformations with a bound $k$ on the maximum distance that needs to be reported. We give a deterministic $O(nk\log k)$ time solution, which we then improve by careful use of randomization to $O(n\sqrt{k\log k}\log n)$ time for sufficiently small $k$. Our randomized solution outputs the correct answer at every position with high probability.

In the k -matches problem, we are given a pattern and a text, and for each text location, the desired output consists of all aligned matching characters if there are k or fewer of them, and any k aligned matching characters if there are more than k of them. This problem is one of several string matching problems that seek not only to find where the pattern matches the text under different “match” definitions, but also to provide witnesses to the match. Other such problems include k -aligned ones, k -witnesses, and k -mismatches. In addition, the solutions to several other string matching problems rely on the efficient solutions of the witness finding problems. In this article we provide a general method for solving such witness finding problems efficiently. We do so by casting the problem as a generalization of group testing, which we then solve by a process we call peeling . Using this general framework we obtain improved results for all of the problems mentioned. We also show that our method also solves a couple of problems outside the pattern matching domain.

Nondeterminism is a fundamental concept of computer science. However, since it is a very abstract concept, teaching and learning nondeterminism is difficult. In this paper we focus on one aspect of the teaching and learning processes of nondeterminism: the extent to which undergraduate students of computer science perceive that nondeterministic automata exhibit nondeterministic behavior, that is, they are unpredictable and inconsistent. First we show that students tend to think of nondeterministic automata as consistent machines; then we show that an explicit intervention can significantly affect students' mental models of nondeterministic automata in the direction of improving their perception of nondeterministic behavior.

Let a text string T of n symbols and a pattern string P of m symbols from alphabet /spl Sigma/ be given. A swapped version T' of T is a length n string derived from T by a series of local swaps, (i.e. t/sup '//sub l//spl larr/t/sub l+1/ and t'/sub l+1//spl larr/t/sub l/) where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i for which there exists a swapped version T' of T where there is an exact matching of P in location i of T'. It has been an open problem whether swapped matching can be done in less than O(mn) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time O(mn). We present an algorithm whose time complexity is O(nm/sup 1/3/ log m log/sup 2/ /spl sigma/) for a general alphabet /spl Sigma/, where /spl sigma/=min(m, |/spl Sigma/|).