11
votes
Accepted
Count number of non-contiguous occurrences in string
A dynamic programming algorithm in $\mathcal{O}(|S| |T|)$ should do the trick.
Let's denote $S = s_1…s_m$ and $T = t_1…t_n$. For $0\leqslant i \leqslant m$, $0\leqslant j \leqslant n$, let $N(i, j)$ ...
- 16k
8
votes
Accepted
Find all substrings that fit the mask with asterisks
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 ...
D.W.♦
- 164k
7
votes
Accepted
Finding the smallest string that contains a given set of substrings
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 ...
- 7,564
6
votes
Accepted
What is an efficient data structure for prefix matching?
A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time.
If you care about constant factors, the only way to know what will be optimal is to try ...
D.W.♦
- 164k
5
votes
Accepted
Maximum number of different substrings in big string
Here is a general solution for an alphabet of size $d \geq 3$ and a string of length $n$.
Every string of length $n$ has $n-\ell+1$ substrings of length $\ell$. Hence the number of different ...
- 278k
5
votes
Accepted
Algorithm: given very large file of strings, find lines containing substring
You can construct a suffix tree for that very large file and once generated the same can be used for querying.
For Suffix tree generation use Suffix Array approach, there are many algorithm to ...
- 119
5
votes
I'm looking for an algorithm to find unknown patterns in a string
Construct the suffix tree of your string, which takes time linear in the length of the string (assuming a finite alphabet). Every inner node represents a repeat, their respective descendant leaves ...
- 72.8k
5
votes
Algorithm to identify contiguous repeated series of lines in a long string
Build suffix tree using Ukkonen's algorithm, this way in $\mathcal O(n)$ you will find all substrings in provided text with indices.
In the case of approximate matching, there is also extended ...
- 9,495
5
votes
Accepted
Algorithm to identify contiguous repeated series of lines in a long string
Under normal circumstances, JVM fills only the last 1024 calls in a stacktrace, and in Dotty/Scalac most stackoverflows have a repeating fragment of length ≈ 70 or less. A stacktrace T of a ...
- 66
5
votes
Accepted
Sampling a uniform distribution of fixed size strings containing no forbidden substrings
Suppose the alphabet is $\{a,b\}$, and you have one forbidden word, $aa$. Suppose we are trying to generate a word of length 3. The first two letters will be distributed uniformly over $ab,ba,bb$. ...
- 278k
5
votes
Accepted
Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?
This can be solved with Aho-Corasick algorithm in $O(nm + Mm)$ time, where $M$ is the number of pairs outputted.
First build the Aho-Corasick automaton for the set of strings in $O(nm)$ time. Then ...
- 1,339
4
votes
Accepted
Minimum number of nucleotides to force duplicate substring
The answer is 66: any sequence of length greater than 66 must contain some repeated substring (as you argue in the question), and there exists a sequence of length 66 where no substring is repeated.
...
D.W.♦
- 164k
4
votes
Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k
Basic idea:
Use 2 pointers to traverse the array: start and end. Both start at the beginning of the array. Try moving end one position at a time and track the maximum subarray length, until the gap is ...
- 186
4
votes
Algorithm to identify contiguous repeated series of lines in a long string
If you consider that “a line of stacktrace” = “a character”, you can use:
http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
One way to solve this problem efficiently is by constructing ...
- 141
4
votes
Algorithm to identify contiguous repeated series of lines in a long string
An efficient string factorization algorithm may help.
Given a string $S$, $n = |S|$ find maximum $p$ such that $S = T^p$ e.g. $T$ concatenated $p$ times, we call $T$ the seed and p the period. This ...
- 41
4
votes
Accepted
Streaming digit-to-digit conversion from decimal to hexadecimal
I don't think this is possible. Changing a high-order digit in a base-10 number -- say, changing 5000000 to 6000000 -- can change bits in its binary equivalent all the way from high-order bits to ...
- 5,489
4
votes
Accepted
How many operations of flipping all brackets on a substring of a string of brackets are needed to make the string 'correct'?
The DP suggested in the comments by Yuval Filmus indeed works: we can solve the problem in $\mathcal{O}(n^{2})$ by DP.
First note that we may assume that intervals are not allowed to overlap. Take ...
- 1,131
4
votes
Is there a formal definition of sub-instances or sub-problems?
I don't think there is a widely-used formal definition, and that this is so for a good reason. Sub-problems or sub-instances are tools used in the process of designing algorithms (for "divide and ...
- 8,323
4
votes
Accepted
Is there a linear-time solution to the minimum window substring problem, provided the characters in the substring must be in order?
Yes, if the length of T can be considered as a constant.
Here is an efficient algorithm.
...
- 39k
4
votes
Accepted
Maximum difference between maximum and minimum frequency in a subarray
Your problem can be solved in linear time in the length of the input string.
Let $s=s_1s_2s_3\ldots$ be your input string. For $0<i\le j \le |s|$, let $n(i,j,c)$ be the number of occurrences of $c$ ...
- 29.6k
4
votes
A more concise Finite Automata for 10 substring?
Your automaton (automata is the plural word) is wrong:
as @Knogger stated, there is no initial state
finite automata (unless generalized) can only have one-letter transitions, so transitions $01$ are ...
- 16k
3
votes
Accepted
Finding the maximum substring for which a given predicate is true
Let's denote $[\exists s: F(s) \wedge |s| = x]$ as $B(x)$. First property of $F$ implies that for any $x > L$
$$B(x) \implies B(x-1)$$
Which by induction implies:
$$B(x) \implies \forall i \in [...
- 1,073
3
votes
What is correct time complexity of the substring generation algo
To be blunt, the Stack Overflow question and its answers illustrate why you want to ask about such things here.
The propsed algorithm clearly does not run in quadratic time.
Since the length $n$ of ...
- 72.8k
3
votes
Accepted
I'm looking for an algorithm to find unknown patterns in a string
Here is a simple search in Python:
...
- 146
3
votes
Accepted
Grammar of words with exactly $k$ prefixes in another grammar
Unfortunately there is no such construction, as the context-free languages are not closed under this operation.
Consider the language $\{ a^nb^n \mid n\ge 1\} \cup \{ a^kb^nc^n \mid k,n\ge 1 \}$.
...
- 30.9k
3
votes
Accepted
Does there exist a subset of substrings for reconstructing another string?
If reusing strings in $A$ is allowed you can solve it with dynamic programming: First, store strings in $A$ in a prefix tree (just a reversed suffix tree link), and recursively detrmine if $S[i:end]$ ...
- 531
3
votes
Is there a formal definition of sub-instances or sub-problems?
Not that I know of. But see here for some common patterns in dynamic programming algorithms: What is dynamic programming about?.
D.W.♦
- 164k
3
votes
Is there a formal definition of sub-instances or sub-problems?
I have also not seen a formal definition, and I have seen subinstance and subproblem used interchangeably, but also seem to remember some people separating them (and can find no evidence to support ...
- 18.2k
3
votes
Accepted
Is there a formal definition of sub-instances or sub-problems?
To add to the other good answers already here consider how subinstances are used in practice. Given an instance (formally a string $x$) we construct another instance (this too we could formally ...
- 771
3
votes
Reconstructing a string from two its partitions into substrings of varying size
This problem, or at least one interesting variant of it, is NP-complete even for binary alphabets and word lengths at most logarithmic in the total number $p$ of partition parts, so it's very unlikely ...
- 5,489
Only top scored, non community-wiki answers of a minimum length are eligible