# Questions tagged [strings]

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

474 questions
Filter by
Sorted by
Tagged with
4 views

### Is solving Binary String Matching equivalent to Solving All type of string matching?

This might be an irritating, naive question, but please bear with me. If an algorithm/code solves the string matching problem for a binary string, does not it imply that the algo/code actually solves ...
38 views

### Construct Binary String Text based on Pattern Text for Worst Case of KMP Algorithm

Given a pattern binary string $P$ of length $m$, if $k$ is a given constant number, construct (provide algorithm/code in c, python) a text string $T$ (binary) of length $c\times m$, such that there is ...
1 vote
53 views

1 vote
38 views

### Determine if string can be constructed from given building blocks

Let's say building blocks are X, Y, XX, YY, XY and YX. Each building block has an associated count ($c_X, c_Y, c_{XX}, \ldots$, $c_i$ can be 0). Given a string $s$ and building block counts, figure ...
1 vote
31 views

### Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B

I've been given the question in the title: Create a data structure that can insert a string S in O(|S|), string may belong to group A or B (or both). The structure should be able to return a string in ...
49 views

1 vote
1k views

### What is the name of the following binary encoding?

S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...] I want to encode / decode natural numbers with the following scheme: Encoding N: For ...
92 views

### What properties must a string satisfy to be a possible output of the Burrows-Wheeler transform?

The Buttows-Wheeler transform is a function that takes a string $S$ to a new string $S'$ and an index $I$. The new string $S'$ is always an anagram (rearrangement) of the input string $S$. However, if ...
1 vote
26 views

### What is the name of the following problem on sets of strings

Given finite sets $A,B,C$ of finite strings, does there exist some $x,y \in A$ and some $z$ such that $x.z \in B$ and $y.z \in C$ hold (where $x.z$ denotes the concatenation of $x$ and $z$)? That is, ...
98 views

### Does creating a deep copy of a string of size N (in python) take space complexity O(N) or O(1)?

My question comes from solving this LeetCode question, in which we are given a string of characters with size N, and one of the solutions is to use a hashmap (dictionary in Python) to count the ...
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 ...
8 views

### Text macros(replacements) based on pre-defined rules

I'm writing a web app that requires a component that let's the user input a piece of text thats automatically formatted based on something the client calls "macros". These macros have a very ...
109 views

### Find all n bit numbers with k ones and unique under circular shift

I am trying to traverse through all uint64_t with k 1s. Then I find that if x and y are circular shifts of each other, they will output the same result. So I'm trying to optimize my code. The problem ...
23 views

### If string x is conjugate to string y, how can you prove that the reverse of x is conjugate to the reverse of y?

I am relatively new to writing proofs and I am stuck trying to prove that if $x$ ~ $y$, then $x^R$ ~ $y^R$. Any help would be appreciated!
44 views

### Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?

In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state: The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
37 views

128 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&...