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
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. -- $...
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
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
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 ...
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
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
Asymptotic running time analysis is not likely to be the best tool to pick between these two algorithms: asymptotic analysis ignores constant factors, and the constant factors will be critical here. The two algorithms have basically the same asymptotic running time, so asymptotic analysis probably isn't very helpful to choose between them.
Instead, the ...
6
Answer. Although I have seen a deleted answer, I still think the construction is linear in the length of the string (considering the alphabet size constant).
Aho Corasick 1975, doi:10.1145/360825.360855
Or perhaps KMP. Aho & Corasick consider pattern matching automata for a finite set of words, forming a tree with back-pointers in case of mismatches=...
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
Despite the different uses of the algoritms, and the various names, I personally would say this is a single algorithm, with different variations. To make this answer more readable, I will add some details.
The basic algoritm global alignment (aka Needleman-Wunsch, below left) compares two strings $x=x_1\dots x_m$ and $y = y_1 \dots y_n$ (with match/mismatch ...
5
A dynamic programming algorithm seems to work.
Given a prefix $X_k = x_1 x_2\dots x_k$ of string $X$ ($X$ is of length $s$, so $X = X_s$), a prefix $Y_m = y_1 y_2 \dots y_m$ of string $Y$ ($Y$ is of length $t$, so $Y_t = Y$), and a length $L$, we determine if there is a subsequence of $X_k$ which is also a subsequence of $Y_m$, such that the sub-sequence is ...
5
I thought for quite some time, but didn't find the problem with doing all of your operations in the most stupid possible way in a trie-like DAG structure:
Add-Prefix-Set
Create a trie of strings from $T$. Connect each leaf node to the root of the old trie.
Complexity: $O(|T|)$
Merge
Unite roots of two structures: make all children nodes of the second root ...
5
The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks.
Buss and Soltys proved NP-completeness of this problem [1] by reducing 3-Partition problem to this problem.
[1]: Buss, Sam, and Michael Soltys. "Unshuffling a square is NP-hard." Journal of Computer and System Sciences 80.4 (2014): 766-...
5
Given a FA $M$ accepting a language $L$, a suffix automaton is one which accepts the language of all suffixes of strings in $L$. In other words for a language $L$ over an alphabet $\Sigma$,
$$
\operatorname{SUFFIX}(L)=\{y\mid\exists x\in\Sigma^* \ (xy\in L)\}
$$
For example, if $L$ is the language denoted by the regex $ab^*a$ we'll have $L=\{aa, aba, abba, ...
5
Say that $F(n)$ occurs at some position if the substring starting at that position is compatible with either $F(n)$ or its complementation. How close can occurrences of $F(n)$ be? Take as an example $F(4) = abaab$. If $F(4)$ occurs at position $p$ then it cannot occur at position $p+1$ or $p+2$, but it can appear at position $p+3$. We let $\ell(n)$ be the ...
5
Rule 110 is a binary rewriting system that can perform universal computation, i.e., it has been proven to be universal. It can be implemented by a finite-state transducer: it needs only finite state.
However, Rule 110 is not a tag system or a cyclic tag system, so this does not provide an instance of a specific binary tag system that is known to be ...
5
It looks like it refers to a substitution, but that the given definition is incomplete.
Anyway, in formal language theory, people often use monoid morphisms between free monoids. To avoid overloading the term "morphism", a monoid morphism from a free monoid $A^*$ into the monoid $2^{B^*}$ of languages of $B^*$ (under concatenation product of languages) is ...
Only top voted, non community-wiki answers of a minimum length are eligible
