# Questions tagged [strings]

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

502 questions
Filter by
Sorted by
Tagged with
12 views

### Flowgarithm for common child program for a beginner (without pointers)

I'm a first year BCA student. Can you help me with flowgarithm of the common child problem (LCS) without pointers
35 views

### Find a substring length $k$ with maximum occurrences

Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string. We want $O(S)$ time complexity in an average case. I think the solution lies in sophisticated ...
61 views

### Longest Fibonacci word

We define Fibonacci words as: $F_0 = a, F_1 = b, F_{n+2} = F_n F_{n+1}$, $a, b$ can be any symbols. How can we find the longest Fibonacci sub-word in a given string in linear time? This question is ...
1 vote
40 views

### Problem identification: splitting string into tokens taken from a given, possible overlapping set

I am facing the following problem in a script I am trying to develop: Given a string and a set of tokens, where the tokens are known and are overlapping (the set can contain the tokens 'a', 'b' and '...
1 vote
40 views

### Simultaneous matching of all Caesar rotations of a pattern in a text

Suppose we have an alphabet of size $S$, a pattern of length $P$ and a text of length $T$. We want to design an algorithm for matching all caesar rotations of the pattern $P$ in the text $T$. The ...
14 views

### KMP search: Can a shift by partial match prefix by non-suffix match lead to exact match?

Consider the following step where 'abaab', upon failed mismatch, 'ab' the prefix is followed by aligning at 'ab' the suffix. What confuses me is the reason for being able to discard the possibility of ...
41 views

### finding the length of the GCD of two strings

Let's say you have two strings: a and b with GCD c. Why is it that ...
1 vote
47 views

### Finding the subset of a dictionary that has the minimum edit distance to a given string

I'm looking for the most efficient way of solving an Levenshtein edit distance problem. We are given as input: A set of strings S of size ...
121 views

### Design an algorithm to predict words based on a skeleton from a given dictionary

I'm working on an algorithm which is permitted to use a training set of approximately 250,000 dictionary words. I have built and providing here with a basic, working algorithm. This algorithm will ...
54 views

### Data Structure for strings on integers

Designing a datastructure which supports the following operations on integers (It can also be visualized as a datastructure on strings, if the alphabets/characters have total ordering) Operations on ...
1 vote
78 views

### Minimum pumping length of a context-free language

I was studying about the minimum pumping length of the language $L$ containing all palindromes over $\{a,b\}$ from this material about the pumping Lemma for CFLs. The productions are as follows: S\...
14 views

### What algrorithm computes a mutally exclusive partitioning from two regulair expressions?

The Question A regular expression, such as AL+[EYI]+, represents a set of strings. ...
52 views

67 views

### Number of bit string interpretations correct?

Suppose you are given a bit string $B[1 ... n]$. Now, suppose that some bits are just padding bits conveying no information, the rest of the bits may be permuted and some meaningful (that is, non-...
1 vote
54 views

### Understanding how the total # of comparisons is derived for the worst case in the "Brute-Force String Matching" algorithm

The Total number of comparisons for the worst case in the "Brute-Force String Matching" algorithm is: (n-m+1) where ...
1 vote
123 views

### Failure function of the Fibonacci strings (The Dragon Book Exercise 3.4.9d)

Exercise 3.4.9 of The Dragon Book defines Fibonacci strings as follows: $s_1 = b$. $s_2 = a$. $s_k = s_{k-1}s_{k-2}$ for $k>2$. Part (d) then poses the following question: Show that the failure ...
152 views

### How can we show that P is not closed under taking all long prefixes?

Let P be the complexity class of languages decidable by Turing machines running in polynomial time. Say a prefix $s$ of a string $x$ is a long prefix (or an L prefix) if $|s|\ge |x|/2$. For a language ...
1 vote
740 views

### time complexity to convert string to integer and vice a versa

just given solution on this post i had mention the time complexity to convert string to int is O(n), also verifying this post now in one of comment fellow SO user, corrected me with example also ...
67 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 ...
1 vote
66 views

1 vote
53 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
36 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 ...
54 views

Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character, The restrictions: $... 0 votes 1 answer 202 views ### Is it faster to use Counting Sort to lexicographically sort characters in a word in Python? Assuming I have very long words, is it worth it to use Counting Sort with its memory overhead to achieve linear time complexity? I wrote a Python function that sorts the characters in a given string ... 1 vote 1 answer 357 views ### Hash / Compression algorithm to shorten text? I desperately need a hash / compression function that is suited to shorten text. The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined ... 2 votes 1 answer 52 views ### Check if a string can be obtained by a sequences of insertion of "abc" Let$a$initially be an empty string. One can transform$a$into$b$in the following way:$a$becomes$a_{left}+$"$abc$"$+a_{right}$, where$a=a_{left}+a_{right}$in a prior state.$a_{left}... 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 ...
103 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
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, ...