# Tag Info

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
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 ...
• 164k
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
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 ...
• 164k
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
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

### 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

### 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
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 ...
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
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
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. ...
• 164k

### 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

### 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

### 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
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
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

### 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
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
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

### 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
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

### 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
Accepted

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

Here is a simple search in Python: ...
• 146
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
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]$ ...

### 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?.
• 164k

### 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
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
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 ...