Questions tagged [substrings]

Questions about algorithms related to substrings, or about properties of substrings.

Filter by
Sorted by
Tagged with
12
votes
1answer
2k views

Counting number of sums from contiguous subarrays of an array

We are given an array $a[1 \ldots n]$ with all $a[i]>0$. Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a[...
10
votes
2answers
4k views

Fast k mismatch string matching algorithm

I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P ...
10
votes
2answers
4k views

An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?

This page about Knuth-Moriss-Pratt Algorithm compared to Boyer-Moore describes a possible case where the Boyer-Moore algorithm suffers from small skip distance while KMP could perform better. I'm ...
10
votes
1answer
772 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: $$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \...
9
votes
1answer
1k views

Given n strings, is one of them a substring of another?

Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$. I would like to know whether any of those strings is a substring of any other string in the collection. In other words, I'd like an ...
8
votes
2answers
3k views

Automaton for substring matching

Given $s$ as a string over some alphabet, what is the best known algorithm to compute a corresponding deterministic finite-state automaton (DFA) that accepts any string that contains $s$? I am mostly ...
7
votes
4answers
3k views

Algorithm Request: "Shortest non-existing substring over given alphabet"

I'm looking for an (efficient) algorithm to solve the following problem: Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
7
votes
2answers
271 views

How many operations of flipping all brackets on a substring of a string of brackets are needed to make the string 'correct'?

I call a string of brackets 'correct' if every opening bracket has a corresponding closing bracket somewhere after it and every closing bracket has a corresponding opening bracket somewhere before it. ...
7
votes
1answer
119 views

Subsequence of one string but not of others

Let $\Sigma$ be an alphabet, and let $x^+,x^-_1,\dots,x^-_n \in \Sigma^*$ be strings over that alphabet. Call a string $s \in \Sigma^*$ good if $s$ is a subsequence of $x^+$ but not a subsequence of ...
6
votes
1answer
1k views

Finding the smallest string that contains a given set of substrings

The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible....
6
votes
1answer
289 views

Sampling a uniform distribution of fixed size strings containing no forbidden substrings

Given a list of "forbidden" words (substrings), an alphabet, and a desired output string length, how would I efficiently sample output strings containing no forbidden word? For short output strings ...
6
votes
1answer
3k views

Find longest common substring using a rolling hash

The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring ...
6
votes
1answer
643 views

Finding a certain prefix of a string

Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a ...
5
votes
4answers
582 views

Is there a formal definition of sub-instances or sub-problems?

A decision problem is denoted as a language $L \subseteq \Sigma^{*}$. For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$. For some ...
5
votes
1answer
5k views

Algorithm to search substring in a circular string?

I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt. However, as far as I ...
5
votes
1answer
542 views

Find all substrings that fit the mask with asterisks

There is a problem. Given string $text$ containing only letters and string $mask$ containing letters and asterisks (*), where asterisk means substitution of zero or more letters, find all substrings ...
5
votes
5answers
11k views

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

I am trying to detect patterns in huge code bases. I managed to filter the entire codebase into a tagged string, as in: ABACBABAABBCBABA The result should be: ABA *3 CBA *2 I'm trying to build / use ...
5
votes
1answer
116 views

String searching, where we allow characters to almost-match

Let $\Sigma= \{1,...,n\}$. Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively. I am looking for an algorithm to test whether $Q$ appears as a ...
5
votes
1answer
5k views

Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ ...
5
votes
0answers
52 views

Highest covering repeated string

Let's say I have the following string: XXXXXAYYYYBYYYYCXXXXXDYYYY We can see that the substring XXXXX is 5 characters long, ...
5
votes
0answers
391 views

Number of distinct substrings

I know how to find the number of distinct substrings for a string (using suffix arrays) and I was wondering if there was a way to find this number for all of its prefixes. I already have an $O(N^2)$ ...
5
votes
0answers
363 views

Understanding the Baeza-Yates Régnier algorithm (multiple string matching, extended from Boyer-Moore)

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand. R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two ...
4
votes
1answer
46 views

Is there a linear-time solution to the minimum window substring problem, provided the characters in the substring must be in order?

Suppose there are two strings, $S$ and $T$, and we want to find the length $l$ of the shortest substring of $S$ which contains all the characters in $T$, in order. (Assume the length of $T$ is bounded,...
4
votes
1answer
761 views

Can not understand idea of the KMP algorithm

I am using Sedgewick's Algorithms (4th ed) to learn Knuth-Morris-Pratt substring search algorithm. The key step is construct the DFA array corresponding to a given pattern. The authors say: The key ...
4
votes
1answer
7k views

Number of distinct substrings in a string

From what I have come to understand, the best way to implement it is to use the suffix array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$. The answer can be obtained by $$ \...
4
votes
2answers
1k views

Fuzzy string matching algorithm with allowed events?

I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions ...
4
votes
0answers
71 views

Sequence where every subset exists as some contiguous subsequence

Given a set (i.e., a collection of distinct elements), how would you find a minimal sequence where every subset of that set can be found as the elements in some contiguous subsequences? The order of ...
4
votes
3answers
372 views

Sum of unique elements in all sub-arrays of an array

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...
3
votes
2answers
2k views

Dynamic programming table for finding similar substrings is too large

Substring Diff Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots q_{j+L-1}...
3
votes
1answer
179 views

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)$?

Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of ...
3
votes
2answers
940 views

Algorithm: given very large file of strings, find lines containing substring

I'm not sure if cs.stackexchange.com is correct place to ask this question but it looks like most relevant. On the job interview I was asked a question: lets say we have a very large file, containing ...
3
votes
4answers
7k views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
3
votes
1answer
155 views

Does there exist a subset of substrings for reconstructing another string?

I am looking for a high performance algorithm to check whether I can reconstruct a given string using a given set of substrings. More details: Let's say our strings are over the alphabet $\Sigma$. ...
3
votes
2answers
350 views

O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?

Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem. If s = little string and S = len(s) b = big string and ...
3
votes
1answer
166 views

Maximum number of different substrings in big string

I'm trying to find the maximum number of different substrings of string consisting only of lowercase letters 'a' - 'z', if the length of string can be up to $5000$ Firstly, I was thinking that the ...
3
votes
2answers
875 views

Which is the proper algorithm to figure repeated substrings of longest total length?

Given a string $S$ and a substring $T$, define the value of $T$ to be the total length (in characters) of all non-overlapping instances of $T$ in $S$. In other words, the value of $T$ is the length ...
3
votes
1answer
88 views

Find the smallest set of strings which "covers" a given set of strings (coverage = containing as substring)

Let $S$ be a finite set of strings and $0 < k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds: $\forall t \in T(k,l): k \leq |t| \leq l$ $\...
3
votes
1answer
280 views

Longest substrings of common length with the same parity

Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions: length of both $A$ and $B$ is equal to $x$; sum of ...
3
votes
2answers
242 views

Drawbacks of repeating a single pattern matching procedure for many patterns

One naive approach in solving multiple pattern matching problem is to call single pattern matching procedure on each of the pattern. There must be some drawbacks in this approach, given the variety ...
3
votes
3answers
377 views

Longest common substring many strings to one

I'd like to find longest common substring (occurrences, start index) between one string and many others. For example source string - "abcdefghijklmncdop" other strings - ["cd", "ghi", "mn", "zw", "...
3
votes
1answer
154 views

Find shortest prefix to generate original string by overlapping

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed). For ...
3
votes
0answers
79 views

What is the intuition behind the "edit sensitive parsing" tree?

If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree ...
2
votes
2answers
3k views

What is an efficient data structure for prefix matching?

I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 ...
2
votes
1answer
54 views

Minimum number of nucleotides to force duplicate substring

There are 4 DNA nucleotides, each represented by one of the letters A, C, G, or T. Assume that they can be arranged in a string e.g. "GATTACA...". I want to figure out the minimum number of ...
2
votes
2answers
138 views

Storage cost of a suffix array

MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size ...
2
votes
1answer
1k views

How is n-gram different from k-mer?

How is n-gram different from k-mer? Both seem to be (n or k) length substrings of a larger string. Are these just terms common with different practitioners? viz. Computer Scientists and ...
2
votes
1answer
152 views

Finding the maximum substring for which a given predicate is true

Given a string $S$ of length $N$ and a string predicate $F$, find the maximum substring, $s$, such that $F(s) = \text{true}$. Assume that $F$ satisfies the following: If $F(g) = \text{true}$, then ...
2
votes
1answer
63 views

terminology for grouping words in a string?

We commonly create sub-groups of strings in one particular algorithm implementation. I just want to know in CS literature is there any standard name for such kind of grouping. For e.g. ...
2
votes
2answers
101 views

Sliding Window Dictionary String Matching

Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every ...
2
votes
3answers
601 views

What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end?

Here are some sequences: '0.66666' [3,0,1,2,2,2,0,1] 'banana' 'bandana' '11221122' I would like to find the index and length of the substring in each which is ...