20
This problem is known as the “minimum common string partition problem.” (More precisely, the answer in the minimum common string partition problem equals the answer in your problem plus 1.) Unfortunately, it is NP-hard, even with the restriction that each letter occurs at most twice in each of the input strings, as is proved by Goldstein, Kilman, and Zheng ...
18
What you are looking for is "approximate near neighbor search" (ANNS) in the Levenshtein/edit distance. From a theoretical perspective, edit distance has so far turned out to be relatively hard for near-neighbor searches, afaik. Still, there are many results, see the references in this Ostrovsky and Rabani paper. If you are willing to consider alternative ...
15
No, unfortunately not. There are even infinite square-free words if your alphabet has at least three symbols.
This apparently natural border (two-element alphabets have only finitely many square-free words) is observed in many places, for instance:
$\{xyyz \mid x,y,z\in \Sigma^+\}$ is co-finite for $|\Sigma|\leq 2$ but not context-free for $\Sigma>2$.
...
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 ...
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 ...
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 ...
12
The data structures you are interested in are metric trees. That is, they support efficient searches in metric spaces. A metric space is formed by a set of objects and a distance function defined among them satisfying the triangle inequality. The goal is then, given a set of objects and a query element, to retrieve those objects close enough to the query.
...
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
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 ...
10
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. -- $...
10
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 ...
9
This is a followup to Tsuyoshi Ito's answer above, summarizing the most relevant portion of the GKZ05 paper he cited.
The paper proves a reduction to the Maximal Independent Set (MIS) problem. Construct a graph $G$ whose vertices are pairs $(i, j)$ such that $a_i = b_j$ and $a_{i+1} = b_{j+1}$. Connect vertices $(i, j)$ and $(k, \ell)$ (where $i≤k$) with an ...
9
The Knuth-Morris-Pratt algorithm does this in linear time without any error.
9
The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum.
In formula:
$\qquad \displaystyle \operatorname{mino}(s, C) =
\begin{cases}
|s| &, |C| = 1 \\
|s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\...
9
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 ...
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
For a CS student, the professor may discourage std::string and ask for char array, so as to teach basics of array. In my school, the teacher asked us to write C routines like strlen, strcmp etc. on our own. It can't get any low level then this (leaving assembly!).
By using array, instead of string, you can learn memory-management, string operations, ...
7
Koenig and Moe's Accelerated C++ and Stroustrup's Programming: Principles and Practice Using C++ are using std::string and other components from the standard library from the start. If I remember correctly, they don't even present C arrays for Koenig and Moe and Stroustrup does it quite late in the book (perhaps even just in an annex).
That approach, ...
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
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.
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
The graph I consider has the valid words for vertices and edges correspond to one-letter substitutions. In this graph the Hamming distance never overestimates the distance but can underestimate it (e.g. between $aa$ and $cc$ in the set of valid words ${aa,ab,bb,bc,cc}$)
You don't need an actual graph, you just need a representation of it. The hard part is ...
6
There's an algorithm named after Manacher's algorithm, which is really fast, a linear time algorithm.
See Wikipedia's reference
Postscript: If you're really familiar with Z Algorithm, you will find that they're alike.
Edit
I've just misunderstood the OP's meaning (but I don't want to delete the proceding information. It's somewhat useful). He means the ...
6
If you really just want to count the number of distinct words in the document, you don't need to save each instance of the word to the hash table.
So, if you find a words that's already in the table, just don't add it there. This means you don't have to deal with chaining as often, which will speed things up.
But you still have to deal with collisions, ...
Only top voted, non community-wiki answers of a minimum length are eligible
