Skip to main content
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)$ ...
Nathaniel's user avatar
  • 15.6k
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.'s user avatar
  • 159k
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 ...
xskxzr's user avatar
  • 7,455
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.'s user avatar
  • 159k
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 ...
Chits's user avatar
  • 119
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 ...
Yuval Filmus's user avatar
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 ...
Raphael's user avatar
  • 72.4k
5 votes

Complexity of a naive algorithm for finding the longest Fibonacci substring

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 $...
Yuval Filmus's user avatar
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 ...
Evil's user avatar
  • 9,455
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 ...
hoopoefret's user avatar
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$. ...
Yuval Filmus's user avatar
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 ...
Laakeri's user avatar
  • 1,339
4 votes
Accepted

How is n-gram different from k-mer?

Yes, they mean the same thing. A n-gram is a sequence of n consecutive things (words, letters, whatever). A k-mer is a sequence of k consecutive things (DNA basepairs). The phrase k-mer is more ...
D.W.'s user avatar
  • 159k
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.'s user avatar
  • 159k
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 ...
memo's user avatar
  • 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 ...
n1r3's user avatar
  • 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 ...
mukel's user avatar
  • 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 ...
j_random_hacker's user avatar
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 ...
Antti Röyskö's user avatar
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 ...
Discrete lizard's user avatar
  • 8,248
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. ...
John L.'s user avatar
  • 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$ ...
Steven's user avatar
  • 29.5k
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 ...
Nathaniel's user avatar
  • 15.6k
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 ...
Raphael's user avatar
  • 72.4k
3 votes
Accepted

I'm looking for an algorithm to find unknown patterns in a string

Here is a simple search in Python: ...
Jacob H's user avatar
  • 146
3 votes

Storage cost of a suffix array

You don't store the actual suffixes in the array. You only store indices, $n$ of them. Each index takes $O(1)$ space in the RAM model (which is what the textbook is using to count space), so in total ...
Yuval Filmus's user avatar
3 votes
Accepted

String searching, where we allow characters to almost-match

You're looking for all instances of $Q$ as a substring of $T$, except that two symbols are still considered to match even if they differ by one, so this is basically a generalization of substring ...
D.W.'s user avatar
  • 159k
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 [...
Dmitri Urbanowicz's user avatar
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 \}$. ...
Hendrik Jan's user avatar
  • 30.7k
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]$ ...
Ameer Jewdaki's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible