# Questions tagged [substrings]

127 questions
Filter by
Sorted by
Tagged with
209 views

### Maximum difference between maximum and minimum frequency in a subarray

Can anyone please help me with a better solution than O(n^3) for this problem? So the problem is given a string, we want to output the substring's length where freqency[c1] - frequency[c2] is MAX. c1 =...
94 views

### Is there an efficient algorithm for finding a minimal common subset of pairwise distinct bits in a set of bit strings?

I am working on an efficient mapping function represented as a directed graph. In essence, it is a sort of radix trie. A path must be formed from a bit string [string hereon] efficiently. To do this, ...
83 views

### Complexity of string comparison vs whitespace-trimmed string comparison

I recently worked on an algorithm which, among other things, checks strings for equality using the classic builtin equality operator: str1 == str2 (I think it ...
1 vote
34 views

### Hints for efficient computation of the maximum length of a binary sequence

Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, ...
1 vote
43 views

### Polynomial algorithm for the «Input Series» Problem

Can you help me design an algorithm to solve the following problem in polynomial time? Let n be a given natural number. We define an input series of length n to be a string of length n which is built ...
1 vote
59 views

### Find repeated patterns in a string via lossy compression

Description The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the ...
1 vote
44 views

### Check if string contains pattern (with respect to one-to-one symbols mapping) [closed]

I'm trying to solve following problem: Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original ...
1 vote
30 views

### Longest substring creating palindromic substring in other string

Given two strings $s, t$, I would liketo find a maximal subsequence of $t$ (denoted as $t'$), such that the concatenation of $t'$ with its reverse ($t'_R$), is a palindromic substring of $s$. I ...
1 vote
67 views

### Palindrome operations on a string

You are given a string S initially and some Q queries. For each query you will have 2 integers L and R. For each query, you have to perform the following operations: Arrange the letters from L to R ...
86 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 ...
42 views

### Number of borders of all substrings in a string

Can you please help with solving the following problem. Given a string $s$, we need to find the number of borders of all its substrings. For a single string we can count all the borders in O(n) time ...
1 vote
64 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$ ...
1 vote
27 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 ...
1 vote
115 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 ...
1 vote
42 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 ...
120 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&...
82 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
63 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
53 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
164 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 ...
28 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 ...
513 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
85 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? ...
620 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 ...
105 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 ...
74 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 ...
40 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 - ...
50 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
192 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
72 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: ...
81 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 ...
312 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
22 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. ...
313 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
210 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
743 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 ...
167 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$. ...
332 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
75 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 ...
48 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 ...
107 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 ...
676 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 ...
42 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
675 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 ...
446 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
42 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
91 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 