# Questions tagged [substrings]

115 questions
Filter by
Sorted by
Tagged with
30 views

### Counting substrings of a string that do not contain a given string

Let's say we have a string $s[0..n-1]$ and a pattern $p[0..m-1]$ with $m < n$. I am looking for an $O(nm)$ solution to the following problem: find the number of substrings of $s$ not containing $p$ ...
26 views

### Has anyone seen the following string classifier discussed?

The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea. Given a set of ...
36 views

### Z-function and the minimum string period

Let $s$ be a string of length $n$. One of the classical solutions to the problem of finding the smallest period $p$ of $s$ (that is, smallest $p$ such that $s$ can be obtained as a concatenation of ...
34 views

### Is this string substitution problem decidable?

We have the following task: Take as input a finite set of string pairs. Each pair represents a substitution. Replace exactly one instance of the left with the right. A substitution can only be ...
43 views

### Number of subsequence with k distinct characters

"A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order." Suppose we have string s="aabca&...
39 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,...
56 views

### Is string spliting formally defined when the string delimiter is an empty string?

Depending on the API/language you use, splitting the string "ABCD" using "" as a delimiter gets you: ...
24 views

### How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n]

I was asked this question today: given a very long string x, which contains only lower case alphabets. A valid substring can only started with [a, b, c, d, e] and ends with [h, i, j, k, l, n] IF we ...
87 views

### Boyer-Moore jump table

I have a pattern $P$ of length $m$, i.e. $P = p_0, p_1, \ldots, p_{m-1}$ which I want to build a simple jump table for (not considering special optimizing cases for now). I only want to build a jump ...
19 views

### Smart String search algorithm

I'm looking for a solution to search for strings in a large text file. I would like to match strings with as many of those words in close proximity as possible. For example, if a query is for the ...
135 views

### Turing Machine substring

I want to create a turing machine that describes the language L={x#y | x,y\in {0,1}* and x is a substring of y}. However I'm not sure how to start writing the transition function δ as I've just gotten ...
78 views

### $\omega$-string avoiding a set of substrings

Given a set of strings $S$ over $\{a,b\}$. How to determine whether there is an infinite sequence consisting of ${a, b}$ (i.e., a $\omega$-string), which doesn't have any string in $S$ as a substring? ...
578 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 ...
98 views

### If we want to map abbreviations of full-English words (e.g. map “Jan” to “January”), how can we identify abbreviations which map to multiple words?

Short Version: How can we construct a trie which maps abbreviations of names-of-the-month to full-month (we map the abbreviation "mar" to "march")? The set of all abbreviations is ...
64 views

### Is there a way to determine whether a list of integers can be a prefix function?

Say you had (0,0,0,1,2,3,4,5,6,7,8,9,10) or (0,1,0,1,0,1,2,3,0,1,0,0,1) Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a ...
31 views

### Best way to find and store difference between two strings

I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - ...
38 views

### Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?

Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong. I have a puzzle: ...
102 views

### finding all cyclic substrings of a string

I have been stuck on this problem for a while now; any help would be appreciated. Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For ...
58 views

### Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?

I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings. Example: Set 1: ...
59 views

### Shortest common cyclic superstring

The shortest common cyclic superstring problem is closely related to the shortest common superstring problem. The difference is that each of the strings in the input set may have an arbitrary rotation ...
164 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 ...
21 views

### What is the shortest superstring for $\{c (ab)^k, (ba)^k, (ab)^k c\}$?

In this paper on PDF page 3, they give $\{c (ab)^k, (ba)^k, (ab)^k c\}$ as an example of an input to the GREEDY algorithm for shortest superstring that causes it to have an approximation ratio of 2. ...
251 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. ...
192 views

### Streaming digit-to-digit conversion from decimal to hexadecimal

I am looking for a streaming algorithm for converting a decimal number to a hexadecimal number. I am assuming the input is a string represention of a decimal number (i.e., each character is a decimal ...
546 views

### Time complexity for calculating the $LPS$ array (failure function) in KMP algorithm preprocessing

I'm studying the Knuth Morris Pratt pattern searching algorithm from here. I want to know the order of computing the $lps$ array in this algorithm - that is the array of longest proper prefixes that ...
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$. ...
281 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 ...
66 views

### Max sum of k contiguous subarrays

The question is: given an array of size $n$ and a number $m$, now our goal is to find AT MOST $m$ contiguous subarrays such that the sum of all these subarrays is the largest. It is also required that ...
39 views

### Is there an algorithm to share parts of strings? [duplicate]

Let's say that we have the strings Hello, World, Hello and World. The algorithm I am ...
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 ...
477 views

### Algorithm to find repeated patterns in a large string

For optimization purposes I'm trying to analyze a large list of executed program commands to find chunks of commands that are executed over and over again. This problem is similar to searching ...
35 views

### Conditions for string substitution commutativity

Let's say I have two substitutions given [a:=b] and [c:=d]. What are some conditions that hold for a,b,c,d ∈Σ* iff forall s∈Σ* s[a:=b][c:=d]=s[c:=d][a:=b] Also you can assume that a,c≠𝜀 but you ...
36 views

### Permutation to maximise strings' common prefix

Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix. Given a set $S=\{(s,w)\}$ of pairs of ...
553 views

### Suffix array and counting distinct substrings of specific length

I am trying to use the suffix array, and the LCP array to count all distinct substrings of a specified length. I started with the algorithm for counting ALL distinct substrings. I solved it after ...
372 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", "...
38 views

### Smallest string containing sets of letters

I am looking for a solution to this problem: Given multiple sets of letters (Set0={a,b,c,d}, Set1={d,e,f,g}, Set2={a,b,e,g}, ...), what is the minimal length of the string containing all the sets. The ...
68 views

### ILP representation of the number of maximal 1 sequences in a row

I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some ...
103 views

### Repeated String Match: need help to understand the maximum number of repeats needed to be looked at

There's this question on LeetCode (link): Given two strings A and B, find the minimum number of times ...
521 views

### Finding often repeating substrings in multiple strings

I'm currently looking for an algorithm to find often repeating substrings in one or multiple strings. However, my search until now was not really successful. I try to illustrate the problem on the ...
321 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 ...
85 views