Questions tagged [substrings]

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

Filter by
Sorted by
Tagged with
4
votes
0answers
46 views

Decide whether two strings $x, y$ can be split into substrings $a,b,c$ such that $x=abc$ and $y=cba$

What is the fastest algorithm for the following problem? Given two strings $x, y \in \Sigma^*$ as input, decide whether there exists strings $a, b, c \in \Sigma^*$, such that $x=abc$ and $y=cba$. By ...
0
votes
0answers
19 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
28 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
25 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
50 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
35 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
115 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
17 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
135 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
147 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 ...
0
votes
0answers
15 views

longest sequence (of same digit) count with k changes allowed

Need to find the longest sequence count from the array, where it's allowed to change k elements. i,e [1,1,3,4,3,3,10] and k=2 the answer should be 5, as k=2 means ...
1
vote
1answer
160 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
142 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$. ...
5
votes
1answer
232 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
64 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
0answers
43 views

Is there an algorithm to compress a string array represented as pointers to a long string to pointers with a compressed version of the long string?

In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g. ...
0
votes
1answer
37 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
90 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 ...
1
vote
1answer
210 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
0answers
31 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
30 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
348 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
279 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
37 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
62 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
66 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
369 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 ...
2
votes
2answers
142 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
67 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
648 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
44 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
48 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
534 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
125 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
112 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
203 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
19 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
2k 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
47 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
184 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
112 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
148 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
3answers
3k 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 ...
1
vote
1answer
821 views

Longest repeated substring

I am trying to solve a problem- Longest repeated substring in a string. Firstly, I built a suffix tree that takes O(n) time and then I traversed the suffix tree to find the deepest internal node. I am ...
5
votes
1answer
484 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
1answer
924 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....
0
votes
0answers
96 views

Suffix Trie with indexes of the last substring

As I understood there is a algorithm ("black box") that build trie from a string by O(n) time complexity, This algorithm use pointer to the first appearance of the substring in the string. Is the a ...
0
votes
2answers
555 views

Smallest length such that all substrings of that length contain at least 1 common character

Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common ...
0
votes
0answers
261 views

Computing substring language on automata

Given a DFA, it is possible to compute the automaton that recognizes the language of its substrings (you can compute it as the automaton that recognizes the suffixes of its prefixes). I would like to ...
3
votes
1answer
118 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 ...