# Tag Info

2

I'll list two possible approaches that might be reasonably effective in practice, though their worst-case running time is no better than what you listed. Indices You can build up an index for each word. Build a hash table. For each word that appears in any clean name, the hashtable maps that word to a list of all dirty names that contain that word. This ...

0

Let's say you are looking for substrings that occur at least $c$ times in each string and have length at least $k$. Furthermore, lets say we're looking for maximally repeated substrings i.e. if $R$ is our solution set of substrings, there exists no pair $r_i, r_j\in R$ such that $r_i$ is a substring of $r_j$. Offline option Construct a generalized suffix ...

5

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 run each string through the automaton - this takes $O(nm)$ time for running the strings through the automaton and $O(Mm)$ time for outputting the matches because ...

1

A shorter superstring is $c(ab)^{k+1}c$, which has length $2k+4$.

3

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 any two overlapping intervals $[a, b)$ and $[c, d)$. WLOG $a \leq c$. Then we can replace the two intervals with the intervals $[a, c)$ and \$[\min(b, d), \max(b, ...

0

Nice question! Here is the problem in more popular terms. Balanced Parentheses A string of parentheses is balanced if we can change it to the empty string by removing substrings "()" repeatedly. For example, empty string, "()" and "(())()((()()))" are balanced but none of "())" and ")()()(" is balanced. It is clear that a balanced string must start with ...

Top 50 recent answers are included