# Questions tagged [strings]

Questions about sequences of symbols, sets thereof and their properties as well as uses.

379 questions
Filter by
Sorted by
Tagged with
84 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 ...
18 views

### Spliting strings into groups of similar strings

I would like to group a list of strings into groups of strings differing by max 1 character: For instance, given: [John, Alibaba, Johny, Alidaba, Mary] I would ...
58 views

### How can you compute the expected edit distance in $O(2^{3n/2})$ time?

In a coding challenge an answer claimed to be able to compute the expected edit distance between two binary strings of length $n$ in $O(2^{3n/2})$ edit distance calculations by dynamic programming. A ...
90 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. ...
47 views

### Can I solve my decision problem in $O(n)$ time?

My algorithm solves a custom string problem but it loops twice making it $O(n^2)$ time. I'm asking here as I'm a beginner in self-learning algorithms. Decision Problem: Given an input list $A$, can ...
18 views

### Lexicographically minimal string rotation

In this page: https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation there is the Booth's Algorithm for lexicographically minimal string rotation but there is no proof. I can't access ...
12 views

### Finding fewest strings that cover $\Sigma^n$ up to $R$ edit operations

Let $\Sigma$ be the alphabet, $0<R<n$ be an integer and let $\Sigma^n$ denote the set of all strings of length $n$ over the alphabet. The task is to find the minimum $m$ such that there exist ...
87 views

### Primitive word and cyclic rotations

Definition. A word $w \in \Sigma^*$ is primitive if $w=u^n \rightarrow n=1$. Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?
21 views

### How to construct a DFA which accepts all the strings endig with aa and no two consecutive b (bb)

I have to construct a DFA which ends with aa and does not contain any pair of b-s. A = {a,b}, {aa,baa,aaa,abaa,babaa,...}. I know how to construct them as separate DFAs but not together merged.
44 views

### Find number of awesome substring of a given binary string

A binary string is given to us and we need to find number of awesome substring of that string .Definition of awesome string : A string is awesome if its length is divisible by number of 1's in it. ...
13 views

### Does this kind of “conversation tree” has a specific name?

Does a Tree of infinite width and depth where each node represents a syntactically valid response to (a node of) a previous response to which it's connected via an edge has a specific name? (It seems ...
54 views

49 views

### How many “compressible” strings are there?

Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this. It is easy to see that almost all ...
21 views

### Little Endian and Decimal numbers

I understand that, for some hex string like 0xF0B0D0, the reverse byte order is 0xD0B0F0 since two hexademical digits represent ...
83 views

### Can we solve this problem more efficiently than trying all possible combinations

Here is the context of the problem I am struggling with. I have a set of strings, for example: ...
78 views

33 views

### Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?

A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply ...
We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity. Can a solution be found in only linear time?