The study of strings is an important combinatorial field that precedes the digital computer. Strings can be very long, trillions of letters, so it is important to find compact representations. Here we first survey various forms of one potential compaction methodology, the cover of a given string x, initially proposed in a simple form in 1990, but increasingly of interest as more sophisticated variants have been discovered. We then consider covering by a seed; that is, a cover of a superstring of x. We conclude with many proposals for research directions that could make significant contributions to string processing in future.

We study a central problem of string processing: the compact representation of a string by its frequently-occurring substrings. In this paper we propose an effective, easily-computed form of quasi-periodicity in strings, the frequency cover; that is, the longest of those repeating substrings u of w , |u| > 1, that occurs the maximum number of times in w. The advantage of this generalization is that it is not only applicable to all strings but also that it is the only generalized notion of cover yet proposed, which can be computed efficiently in linear time and space. We describe a simple data structure called the repeating substring frequency array (ℛ𝒮ℱ array) for the string w, which we show can be constructed in 𝒪(n) time and 𝒪(n) space, where |w| = n. We then use ℛ𝒮ℱ to compute all the frequency covers of w in linear time and space. Our research also allows us to give an alternate algorithm to compute all non-extendible repeating substrings in w, also in 𝒪(n) time and space.

In this paper we focus on a total (but non-lexicographic) ordering of strings called V-order. We devise a new linear-time algorithm for computing the V-comparison of two finite strings. In comparison with the previous algorithm in the literature, our algorithm is both conceptually simpler, based on recording letter positions in increasing order, and more straightforward to implement, requiring only linked lists.

BACKGROUND: DNA microarrays have become ubiquitous in biological and medical research. The most difficult problem that needs to be solved is the design of DNA oligonucleotides that (i) are highly specific, that is, bind only to the intended target, (ii) cover the highest possible number of genes, that is, all genes that allow such unique regions, and (iii) are computed fast. None of the existing programs meet all these criteria. RESULTS: We introduce a new approach with our software program BOND (Basic OligoNucleotide Design). According to Kane's criteria for oligo design, BOND computes highly specific DNA oligonucleotides, for all the genes that admit unique probes, while running orders of magnitude faster than the existing programs. The same approach enables us to introduce also an evaluation procedure that correctly measures the quality of the oligonucleotides. Extensive comparison is performed to prove our claims. BOND is flexible, easy to use, requires no additional software, and is freely available for non-commercial use from http://www.csd.uwo.ca/∼ilie/BOND/. CONCLUSIONS: We provide an improved solution to the important problem of oligonucleotide design, including a thorough evaluation of oligo design programs. We hope BOND will become a useful tool for researchers in biological and medical sciences by making the microarray procedures faster and more accurate.

Unique substrings appear scattered in the stringology literature and have important applications in bioinformatics. In this paper we initiate a study of minimum unique substrings in a given string; that is, substrings that occur exactly once while all their substrings are repeats. We discover a strong duality between minimum unique substrings and maximum repeats which, in particular, allows fast computation of one from the other. We give several optimal algorithms, some of which are very simple and efficient. Their combinatorial properties are investigated and a number of open problems are proposed.

This paper aims to provide an analytical view in estimating the cost of Spam 2.0. For this purpose, the authors define the web spam lifecycle and its associated impact. We also enlisted 5 stakeholders and focused on defining 5 cost calculations using a large collection of references. The cost of web spam then can be calculated with the definition of 13 parameters. Detail explanations of the web spam cost impacts are given with regards to the main four stakeholders: spammer, application provider, content provider and content consumer. Ongoing research in developing honey spam is also presented in this paper.

Suppose a set W of strings contains exactly one rotation (cyclic shift) of every primitive string on some alphabet Σ. Then W is a circ-UMFF if and only if every word in Σ has a unique maximal factorization over W. The classic circ-UMFF is the set of Lyndon words based on lexicographic ordering (1958). Duval (1983) designed a linear sequential Lyndon factorization algorithm; a corresponding PRAMparallel algorithmwas described by J. Daykin, Iliopoulos and Smyth (1994). Daykin and Daykin defined new circ-UMFFs based on various methods for totally ordering sets of strings (2003), and further described the structure of all circ-UMFFs (2008). Here we prove new combinatorial results for circ-UMFFs, and in particular for the case of Lyndon words. We introduce Acrobat and Flight Deck circ-UMFFs, and describe some of our results in terms of dictionaries. Applications of circ-UMFFs pertain to structured methods for concatenating and factoring strings over ordered alphabets, and those of Lyndon words are wide ranging and multidisciplinary.

A repeat in a string is a substring that occurs more than once. A repeat is extendible if every occurrence of the repeat has an identical letter either on the left or on the right; otherwise, it is maximal. A multirepeat is a repeat that occurs at least mmin times (m⩾ 2) in each of at least q ⩾ 1 strings in a given set of strings. In this paper, we describe a family of efficient algorithms based on suffix arrays to compute maximal multirepeats under various constraints. Our algorithms are faster, more flexible and much more space-efficient than algorithms recently proposed for this problem. The results extend recent work by two of the authors computing all maximal repeats in a single string.

We give a space-efficient simple algorithm for computing the Lempel-Ziv factorization of a string. For a string of length n over an integer alphabet, it runs in O(n) time independently of alphabet size and uses o(n) additional space.

Given a string $\s{x}=\s{x}[1..n]$, a repetition of period p in {\mbox{\boldmath x}} is a substring ${\mbox{\boldmath u}}^r = \break {\mbox{\boldmath x}}[i..i\+ rp\- 1]$, $p = |{\mbox{\boldmath u}}|$, $r \ge 2$, where neither ${\mbox{\boldmath u}} = {\mbox{\boldmath x}}[i..i\+ p\- 1]$ nor ${\mbox{\boldmath x}}[i..i\+ (r\+ 1)p\- 1]$ is a repetition. The maximum number of repetitions in any string {\mbox{\boldmath x}} is well known to be $\Theta(n\log n)$. A run or maximal periodicity of period p in {\mbox{\boldmath x}} is a substring ${\mbox{\boldmath u}}^r{\mbox{\boldmath t}} = {\mbox{\boldmath x}}[i..i\+ rp\+ |{\mbox{\boldmath t}}|\- 1]$ of {\mbox{\boldmath x}}, where ${\mbox{\boldmath u}}^r$ is a repetition, {\mbox{\boldmath t}} is a proper prefix of {\mbox{\boldmath u}}, and no repetition of period p begins at position $i\- 1$ of {\mbox{\boldmath x}} or ends at position $i\+ rp\+ |{\mbox{\boldmath t}}|$. In 2000 Kolpakov and Kucherov [J. Discrete Algorithms, 1 (2000), pp. 159–186] showed that the maximum number $\rho(n)$ of runs in any string {\mbox{\boldmath x}} is $O(n)$, but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data strongly suggesting that $\rho(n) < n$. Related work by Fraenkel and Simpson [J. Combin. Theory Ser. A., 82 (1998), pp. 112–120] showed that the maximum number $\sigma(n)$ of distinct squares in any string {\mbox{\boldmath x}} satisfies $\sigma(n) < 2n$, while experiment again encourages the belief that in fact $\sigma(n) < n$. In this paper, as a first step toward proving these conjectures, we present a periodicity lemma that establishes limitations on the number and range of periodicities that can occur over a specified range of positions in {\mbox{\boldmath x}}. We then apply this result to specify corresponding limitations on the occurrence of runs.

We have illustrated that the superior asymptotic complexity of linear time suffix sorting algorithms does not readily translate into faster suffix sorting, compared to implementations of supralinear algorithms. We have also resolved the ambiguity surrounding the practicality of the Algorithm KA: it is slower than supralinear approaches on real data. We described several optimizations to the O(n) KS algorithm that significantly improve performance for real world inputs, but still fall short of some supralinear approaches. It is worth noting that most of the optimizations we describe could also be applied to Algorithm KB, which may then outperform the well tuned suffix sorter of Manzini and Ferragina (2004).

A number of approaches to the measurement of program quality or ‘style’ have recently been described in the computing literature. This article discusses criteria which may be considered for the evaluation of these and other approaches, and for the development of new ones.

The representation of a tree by a right-threaded binary tree, as described for example by Knuth (1968, pp. 332 ff), is extended to permit representation of ‘hierarchic structures’ (directed graphs without circuits). This representation corresponds to a compact storage scheme useful both for ascent and descent of the hierarchy.