Questions tagged [substrings]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
36 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,...
1
vote
1answer
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: ...
1
vote
1answer
20 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 ...
1
vote
0answers
47 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 ...
2
votes
0answers
17 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 ...
0
votes
0answers
86 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 ...
1
vote
1answer
77 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? ...
5
votes
4answers
563 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 ...
0
votes
2answers
94 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 ...
2
votes
1answer
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 ...
0
votes
0answers
26 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 - ...
2
votes
1answer
34 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: ...
1
vote
1answer
83 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 ...
1
vote
1answer
54 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: ...
2
votes
0answers
57 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 ...
3
votes
1answer
136 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 ...
1
vote
1answer
19 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. ...
7
votes
2answers
222 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. ...
1
vote
2answers
179 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 ...
1
vote
1answer
457 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 ...
3
votes
1answer
152 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$. ...
6
votes
1answer
269 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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
2
votes
2answers
100 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
1answer
397 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 ...
0
votes
1answer
34 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 ...
2
votes
0answers
35 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 ...
1
vote
1answer
508 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 ...
3
votes
3answers
331 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", "...
1
vote
0answers
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 ...
1
vote
1answer
66 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 ...
1
vote
1answer
91 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 ...
1
vote
2answers
461 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 ...
3
votes
2answers
280 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
76 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$ $\...
2
votes
2answers
1k 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 ...
5
votes
0answers
48 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, ...
1
vote
1answer
50 views

Grammar of words with exactly $k$ prefixes in another grammar

Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that $$ L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\} $$ where $\text{Pref}(w)$ is the set ...
-3
votes
2answers
661 views

DFA accept 00 as a substring

How can design this question if we have an equation like that ={wxw | w={0,1}* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for ...
3
votes
1answer
140 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 ...
0
votes
1answer
131 views

String Search - how to find the “most” accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
3
votes
1answer
273 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 ...
2
votes
1answer
21 views

Approximating unique string occurrences using a small, fixed amount of memory

Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track ...
2
votes
1answer
4k views

Convert given string to Palindrome with given substring

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other ...
1
vote
1answer
61 views

A hangman variation: determining a string by guessing substrings contained in it

I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I ...
4
votes
3answers
244 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: ...
2
votes
0answers
153 views

Counting subarrays where each number either doesn't occur or occurs odd number of times

We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times. ...
2
votes
1answer
150 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 ...
3
votes
4answers
6k 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 ...