Share Your Experience: Take the 2024 Developer Survey

# 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
49 views

### Multitape Turing Machine to accept power of 2 length 0's string?

I have been trying to find a multitape Turing Machine in order to accept a input string which consists on 0's and whose length is a power of 2: However, Im getting troubble finding it, because I dont ...
27 views

### How to compute an inverse suffix array $ISA$ from a suffix array $SA$ efficiently?

I cannot help but wonder: how to compute an inverse of a suffix array, preferably in linear time? For $ISA$, it holds that $ISA[SA[i]] = i$.
19 views

### What sub-sequences do strings for the standard scientific units have in common?

As motivation, a Space Craft known as the Mars Climate Orbiter failed in the year 1999. The failure occurred because the distinction between pound-force seconds and newton-seconds was made as an ...
20 views

### Proof Closer String/Consensus String/Center String is NP-hard

Given are n gene sequences (words over the alphabet {A, T, C, G}), each of length m. Find a gene sequence (of length m) that minimizes the maximum distance to all given gene sequences. Here, distance ...
• 13
26 views

### Use case for string matching in a 2 by n grid

In a 2 by n grid there is a character in each cell. A path can start at any cell and then you can move to right or down. This way each path will denote a string written by characters on cells visited ...
83 views

### Repeated Substring Pattern

I've been working on the following challenge on LeetCode: Problem: Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together....
• 123
13 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
70 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 ...
• 183
96 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 ...
• 183
1 vote
77 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 '...
• 111
1 vote
43 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 ...
• 441
20 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 ...
• 101
52 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
72 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 ...
• 411
375 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 ...
• 99
60 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 ...
• 118
1 vote
85 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\...
• 113
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. ...
61 views

• 65
70 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
72 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 ...
• 23
1 vote
135 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 ...
• 13
160 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
1k 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 ...
• 111
80 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 ...
• 291
1 vote
70 views

1 vote
54 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 ...
• 175
1 vote
37 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 ...
55 views

### Delete consecutive characters and add zeros at the end with a restriction

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: \$...
• 21