Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
399
questions
0
votes
1answer
36 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 letters grouped in the 2nd stack,...
-4
votes
0answers
45 views
String concatenation in python [closed]
In c we use strcat() function. I want to use concatenation in python. What is the function I should use in python?
0
votes
2answers
80 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 ...
2
votes
1answer
60 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 ...
1
vote
0answers
42 views
Number of words of length n for special language
Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties:
if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
5
votes
1answer
31 views
Isn't this Commentz-Walter algorithm buggy?
I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible ...
-1
votes
0answers
26 views
Strings and Lcp
We are given a string S with |S|=N
We have to answer Q queries
Each query has an integer x as input
We have to report
$\sum_{i=x}^n LCP(i,x)$
Where Lcp(i,x) denotes the length of the largest ...
3
votes
1answer
105 views
Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other
I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two ...
1
vote
1answer
37 views
Strings of infinite length?
Suddenly a thought came to my mind and I thought of resolving it as follows.
We know that:
String is a finite sequence of symbols from an alphabet $\Sigma$
i.e. we cannot have an infinite sequence ...
0
votes
2answers
30 views
Efficient way to concatenate strings to find specific split up values
I'm working with a list of objects ("Section") that contains a string value among other fields. The strings in all of the sections can be concatenated to form the complete text. I am, however, wanting ...
1
vote
0answers
30 views
What is the appropriate term for the “string splitting” problem?
To be clear, I didn't hear of this in any particular venue, and so can't point you to one.
Two variants that I can bring you:
String spitting
Given a string (sequence of elements), and a function ...
0
votes
0answers
20 views
Best way to find and store difference between two strings
I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - ...
1
vote
1answer
50 views
Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters)
You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern:
X1,X2,X3...Xn,Xn,...X3,X2,X1
where ...
0
votes
0answers
30 views
How would I make sure my compressed string has the smallest length possible?
I'm trying to make a function that takes a string and compresses the repeating blocks. The code I'm using is implemented in such a way that a single character like 'a' would be converted to '1(a)' ...
2
votes
1answer
29 views
Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?
Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong.
I have a puzzle: ...
1
vote
1answer
39 views
Are there search algorithms that perform better on a Rope than a String?
I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not ...
1
vote
1answer
35 views
finding all cyclic substrings of a string
I have been stuck on this problem for a while now; any help would be appreciated.
Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For ...
1
vote
0answers
72 views
Should a prefix tree (trie) node store only a single character or a string?
I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters.
Storing strings is for sure more space-efficient and ...
2
votes
1answer
45 views
Given a list of strings, find every pair $(x,y)$ where $x$ is a subsequence 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 subsequence of $y$. We can assume all strings are of ...
1
vote
0answers
55 views
Fastest way to find a substring 'ab' inside a string 'abab'
Let $A$ be an input alphabet - a finite set of symbols. Elements of $A$ are called the characters.
The alphabet I am interested in is the set of all ordinary letters ...
3
votes
3answers
162 views
Sorting array of strings (with repetitions) according to a given ordering
We get two arrays:
ordering = ["one", "two", "three"]
and
...
1
vote
1answer
50 views
Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?
I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings.
Example:
Set 1:
...
3
votes
0answers
37 views
Why does it take more than the original alphabet to generate sets of strings?
I am reading Computability by Nigel Cutland and I'm stumped on a brief statement about generating particular sets of strings that is not explained or given any examples.
First, here are some ...
3
votes
1answer
118 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 ...
0
votes
0answers
24 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 ...
4
votes
2answers
209 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 ...
7
votes
2answers
144 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. ...
2
votes
1answer
125 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 ...
0
votes
0answers
23 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 ...
1
vote
0answers
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 ...
5
votes
1answer
94 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?
1
vote
1answer
45 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.
1
vote
1answer
57 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.
...
0
votes
0answers
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 ...
3
votes
1answer
57 views
Efficiently extendable hash function?
I'm wondering whether there exist any good hash functions with the following property: Assume that $x$ is some string over some alphabet $A$, then given $H(x)$ we can compute in $O(1)$ time both $H(ax)...
0
votes
0answers
24 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
...
3
votes
1answer
143 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$.
...
3
votes
1answer
163 views
Find the closest string to a fixed set of strings
I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the ...
5
votes
0answers
85 views
Find the 'best' longest common subsequence
I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and ...
3
votes
1answer
51 views
Evaluating predicate on binary strings
Consider two unknown binary strings $$X = x_{1} x_{2} \dots x_{n^{2}}, \quad Y = y_{1} y_{2} \dots y_{n^{2}}, \quad x_{i}, y_{i} \in \{0, 1\} .$$ We may request a string $Z = z_{1} z_{2} \dots z_{n^{2}...
3
votes
1answer
65 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 ...
0
votes
0answers
27 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 ...
2
votes
1answer
89 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:
...
3
votes
2answers
120 views
Why is the lower bound for sorting strings Ω(d + nlogn)?
I'm taking an Advanced Algorithms course. I'm currently studying efficient algorithms for sorting strings. In this chapter, it is provided a lower bound for the time complexity of $\Omega(d + n\log{n})...
1
vote
0answers
97 views
Finding bounded lexicographically largest string of digits but not larger than other with counted substitutions
The problem comes from the book текстовые и жадные алгоритмы (String and greedy algorithms) by a fairly unknown Russian computer scientist Николай Сухоруков.
We are given two numbers $A$ and $B$ of ...
2
votes
0answers
23 views
String to small integer mapping without collision
Is there any good approach to devise a mapping of limited number of strings $N_1 << 2^{15}$ to integers less than $2^{15}$ without conflicts?
Strings are quite often of the form of prefix + ...
-1
votes
1answer
50 views
How do you define and parse variables (free or bound) from user-entered strings?
I'm writing an application in which the user might enter expressions such as $\text{lim}_{i \in I} \beta(i)$ where $\beta$ is a functor. That's just an example, the expressions, which contain ...
5
votes
1answer
237 views
Sampling a uniform distribution of fixed size strings containing no forbidden substrings
Given a list of "forbidden" words (substrings), an alphabet, and a desired output string length, how would I efficiently sample output strings containing no forbidden word?
For short output strings ...
2
votes
1answer
83 views
Does this shuffle have non-zero probability for all permutations?
I was trying to do some code golf, when I created the following algorithm to shuffle a string:
...
0
votes
2answers
85 views
Fastest algorithm to find whether a list contains a word?
Given an unordered list of words, what's quickest way to test whether a certain word is in that list?
I can't think of another way to do this other than just going through each element in the list ...
