Questions tagged [substrings]

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

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
380 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
310 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
0answers
42 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, ...
3
votes
0answers
76 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
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 ...
2
votes
0answers
26 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 ...
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 ...
2
votes
0answers
86 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
3answers
2k 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
0answers
58 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 ...
1
vote
0answers
36 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
0answers
430 views

most efficient way to compute number of anagrams of a string

This is a question from Hackerrank. Given a string S, find the number of "unordered anagrammatic pairs" of substrings. In other words, find the number of unordered pairs of substrings of S that are ...
1
vote
0answers
42 views

Why is the second while loop in KMP not a conditional statement?

When building the partial match table for KMP: ...
0
votes
0answers
14 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 ...
0
votes
1answer
79 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 ...
0
votes
0answers
42 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
0answers
29 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 ...
0
votes
1answer
99 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 ...
0
votes
0answers
94 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
0answers
233 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 ...
0
votes
0answers
50 views

Why is step 4 and 5 necessary in this Cycle Cover Superstring Algorithm?

(Shortest Common Superstring: Input: A set S = {s1, . . . , sn} of strings over an alphabet Σ. Feasible solutions: Each superstring w of S, i.e., each string w that contains all strings $s_i$ ∈ S as ...
0
votes
0answers
169 views

Algorithm to compute string prefix similarity

Given a string, how to get the its prefix similarity? I use an example to explain what I mean by string prefix similarity. Say, s = "ababaa". We take all its suffixes, that is, "ababaa", "babaa", "...
-3
votes
2answers
497 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 ...