15
You can compute the suffix array in linear time with the DC-3 Algorithm. This is a super-cool fancy algorithm that can be implemented in 50 lines of readable C++ code - one of my all-time favorites. The source code is contained in the original paper. If you can compare two characters in constant time and the alphabet size is $n^{O(1)}$, then the DC3 ...
15
The problem is surprisingly non-trivial. First, two brute force algorithms. A square ("repeated pattern") is given by its length $\ell$ and position $p$, and takes time $O(\ell)$ to verify. If we go over all $\ell$ and $p$, we obtain an $O(n^3)$ algorithm. We can improve on that by first looping over $\ell$, and then scanning the string with two running ...
14
Let $m$ and $n$ be the lengths of two given strings,
Linear time assuming the size of the alphabet is constant.
Yes, the longest common substring of two given strings can be found in $O(m+n)$ time, assuming the size of the alphabet is constant.
Here is an excerpt from Wikipedia article on longest common substring problem.
The longest common substrings of a ...
13
A quick recap first. We are looking for a pattern $P[1\ldots m]$ in a string $S[1\ldots n]$. The Rabin-Karp algorithm does this by defining a hash function $h$. We compute $h(P)$ (that is, the hash of the pattern), and comparing it to $h(S[1\ldots m])$, $h(S[2\ldots m+1])$ and so on. If we find a matching hash, then it is a potential matching substring.
The ...
12
I suggest a variation of distribution counting:
Read the text and insert all the word encountered into a trie, maintaining in each node a count, how often the word represented by this node has occured. Additionally keep track of the highest word count say maxWordCound . -- $O(n)$
Initialize an array of size maxWordCount. Entry type are lists of strings. -- $...
12
Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space. These are essentially compressed suffix arrays or suffix trees, which have a lot of literature.
Basic substring search can be o(k) or o(k log n) in time for length k, depending on what data structures are chosen (different types of rank/...
12
Denote the arrays by $A,B$, and suppose they are of length $n$.
Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space:
Compute the minimum values of both arrays, and check that they are identical.
Compute the second minimum values of both arrays, and check that they are identical.
And so on.
Computing the ...
11
Yes, in practice you can get by fine with just letting the computations overflow. You are effectively working modulo $2^{32}$. It also has the advantage of not requiring an (expensive) modulo computation. However, it lacks some of the theoretical performance guarantees. You need to be very careful with the choice of the base (in this case: $10$) with respect ...
11
Enumerate all possible rotations of the queue. Take the lexicographically first of them. Use this as your representative. If you want a short index into a hash table, take the hash of that. Then any two equivalent queues will get the same representative / same index.
If the queue has $n$ items, implementing this naively takes $O(n^2)$ time. However, it ...
9
Create a temporary source string by concatenating itself together until the length of the source string is at least twice the length of the search string. The source string must be concatenated at least once.
Then perform a simple (non-circular) search on that temporary string.
9
Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list:
Read the list in chunks of $k$, convert them to strings, and sum the chunks.
Creating each chunk takes time $\Theta(1+2+\cdots+k) = \Theta(k^2)$, and we do this $n/k$ times, for a total of $\Theta(nk)$. ...
8
For a text of length $n$ we have up to $1+{ n+1 \choose 2}$ different substrings, however there are only $n+1$ suffixes (for every suffix you can pick the position where it starts).
I assume you consider the compressed suffix tree (edge labels are words). This is a tree with $n+1$ leaves and every internal node has at least two children. Thus we have less ...
8
Lempel and Ziv proved that under some reasonable assumptions, the limiting rate of their algorithm is equal to the entropy of the text. That means that in the limit, the output should be completely random. Random text cannot be compressed (on average), so you should expect that if you take a long text and apply Lempel-Ziv twice, then the second time wouldn't ...
8
Yes, there is a more efficient algorithm. Your algorithm can take exponential time.
You can check whether there exists any match in $O(nm)$ time, where $n$ is the length of text and $m$ is the length of mask, and find all matches in $O(n^2m)$ time. I'll show two solutions, one using dynamic programming and one using graph search. You can pick whichever ...
7
Assuming you want disjoint palindromes, this is known as the PALSTAR problem, and there is a linear time algorithm by Zvi Galil and Joel Seiferas. A Linear-Time On-Line Recognition Algorithm for ``Palstar'.
You can find an explanation of the algorithm in the book here: Text Algorithms (look at linked page and the preceding pages).
If you are ok with a ...
7
Hendrik Jan is correct about the Knuth-Morris-Pratt algorithm (warning, wikipedia doesn't explain it particularly well, a text on algorithms is probably a better bet). The failure function can be used to extract a DFA that can perform the string matching. It's not immediately obvious that the failure table is a DFA, but with very little work the transition ...
7
I've never seen this data structure before. However, it doesn't seem like a good choice for storing a set of words, for most purposes. I see three significant disadvantages:
Performance. Looking up a word in this data structure can potentially be quite slow. In particular, when looking up a word of length $n$, checking whether it contains a particular ...
7
The naive approach would be building histograms of both strings and checking whether they are the same. Since we are not allowed to store such a data structure (whose size would be linear to the size of the alphabet) that could be computed in one pass, we need to count the occurences of each possible symbol after the other:
function count(letter, string)
...
6
A larger alphabet is usually a drawback. However there are algorithms that can deal with this as long as the alphabet size is $n^{O(1)}$.
Ukkonen's algorithm runs only in $O(n)$ if the alphabet size is a constant but it is $O(n \log n)$ without this assumption. However, there are alternatives. You can compute the suffix-array of a text in linear time with ...
6
Here is the clean presentation (after going in circles around it).
First you consider all substrings of S that are in M*. From that you
build a trie, which may be understood as a tree structured FA that
recognizes these substrings. You build it so that you complete first the transitions of nodes that are closest to the root. As soon as you have a node from ...
6
There are many "complete bases" for operations on strings. One is based on the representation
$$ \Sigma^* = \epsilon + \Sigma \Sigma^*. $$
In words, a string is either empty or is composed of a character and a string. In order to use this representation, we need the following functions:
nil – the empty string
cons(x,s) – the string consisting of the ...
6
You can build a suffix tree in linear time and check if there's an inner node that corresponds to a full string (constant time per node).
In more detail, assume we are given strings $s_1, \dots, s_n \in \Sigma^*$.
Build a (generalised) suffix tree of $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ with $n$ pairwise distinct terminal markers $\$_1,\dots,\$_n \notin \...
6
I think the Aho-Corasick algorithm is your best bet here. The algorithm is designed to solve the set matching problem (essentially the one you've defined), in which you want to determine which elements of a set of substrings, L, can be found in a longer string, S.
It runs in time $O(n + m + z)$, where $n = \sum \limits_{l \in L} |l|$ (the total combined ...
6
Edit distance is definitely not the way to proceed. The standard approach toward near-identical document deduplication is to compute hashes of shingles. Here's one way to do it:
Compute a set of k-shingles (say 30 char shingles) for each document
Compute min-hashes for the documents
Use locally-sensitive hashing to look-up similar documents when inserting ...
6
This problem is called shortest superstring problem. John Gallant, David Maier and James Astorer proved it is NP-hard in 19791.
Given two strings $A$ and $B$, let $|A|$ denote the length of $A$, and let $S(A,B)$ denote the shortest superstring of $A$ and $B$ where $A$ occurs before $B$. It is easy to reduce this problem to travelling salesman problem, ...
5
What you want to solve is a string matching problem. Wikipedia (and any textbook on the matter) contains a rich list of algorithms with their respective runtimes.
Be aware that they give worst-case runtimes. Different algorithms behave differently on natural text; some perform better because of the large alphabet and some worst because of its repetitive ...
5
I will try (1) and go for infinite (the bonus).
The finite case is called the code problem: finding possible decompositions is like decoding. Its classical algorithm is called Sardinas–Patterson. It is not immediately clear it is a finite search space. The lengths of the decomposition might be long. Still it is not Post Correspondence as that has additional ...
5
Using Yuval's reduction, the problem can be reformulated as "Find the largest range $(i,j)$ in a binary string $S \in \{0,1\}^*$ such that the number of $1$s contained in the range is $\leq K$" (see this question).
The idea is to start with an initial valid range $(0,j)$ of length $maxlen$ and then shift the "window" $(i,i+maxlen)$ to the right, checking at ...
5
One can reduce your problem to the following. Given a sequence of $N$ numbers, find a contiguous subsequence of length at most $K+1$ having maximal sum. This problem, in turn, is solvable in time $O(N)$.
What's the connection between your problem and mine? Let the positions of the mistakes be $I_1,\ldots,I_t$, and add $I_0 = 0$, $I_{t+1} = N+1$. The ...
5
Suffix arrays can be used for this problem. They contain the starting positions of each suffix of the string sorted in lexicographic order. Even though they can be constructed naively in $O(n\log n)$ complexity, there are methods to construct them in $\Theta(n)$ complexity. See for example this and this. Let us call this suffix array SA.
Once the suffix ...
Only top voted, non community-wiki answers of a minimum length are eligible
