# Questions tagged [strings]

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

507 questions
Filter by
Sorted by
Tagged with
1 vote
480 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 ...
• 145
1 vote
37 views

### How many strings of length |w| are unrelated?

For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated? A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically ...
150 views

### Why is KMP preprocessing O(N)?

My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from ...
• 21
64 views

### Given start strings, find simplest DAG that constructs target strings by concatenation

Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,...
• 251
167 views

• 13
1 vote
105 views

### A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS). I) Vectors A vector have a axiomatic ...
• 141
34 views

### How do you prove these string/number radix encoding/decoding algorithms work?

A while back I learned of these great algorithms: ...
• 2,243
108 views

### Binary string satisfying several constraints

I'm trying to solve this problem, but without success. Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several ...
• 103
1 vote
282 views

### Minimum number of given operations in order to group letters in a string

Description Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be ...
152 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 ...
92 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 ...
• 123
1 vote
70 views

• 221
83 views

### Inverse of Burrows-Wheeler

We can invert the Burrows-Wheeler with this method: The inverse can be understood this way. Take the final table in the BWT algorithm, and erase all but the last column. Given only this ...
• 345
179 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$. ...
• 499