Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
379
questions
3
votes
1answer
84 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
18 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 ...
3
votes
1answer
58 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
90 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. ...
0
votes
0answers
47 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
18 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
87 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
21 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
44 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
54 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
19 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
135 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
36 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
74 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
47 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
49 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
21 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
83 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
78 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
92 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 + ...
0
votes
1answer
43 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
217 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
76 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
60 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 ...
1
vote
0answers
17 views
Algorithm for searching string with wildcards
I'm trying to find efficient algorithm for checking if string with wildcards contains given substring.
The parts of the string are separated with a "." character.
So for example I have
...
0
votes
0answers
41 views
Is there an algorithm to compress a string array represented as pointers to a long string to pointers with a compressed version of the long string?
In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g.
...
0
votes
0answers
12 views
String filtering - process hundreds to millions of filters
What would be the most efficient way (whether with algorithims, cpu(s), DBs & SQL, distributed computing, etc) to process many strings, say ~1000/minute, and filter each string over 100s to ...
0
votes
0answers
39 views
Finding an substring in an infinite sequence
I'm trying to find a substring in an infinite sequence of numbers (Similar to Substring in a infinite sequence of numbers) and am a little stuck on improving my algorithm. I know there is already an ...
0
votes
1answer
35 views
Is there an algorithm to share parts of strings? [duplicate]
Let's say that we have the strings Hello, World, Hello and World. The algorithm I am ...
2
votes
2answers
90 views
Sliding Window Dictionary String Matching
Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every ...
0
votes
0answers
8 views
Count compound words with an ambiguous decomposition
I have a set of words $D$, and I make compound words by concatenating a fixed number $n$ of words from $D$ (repetitions are allowed). Let's call such words $n$-compounds. I want to know how many ...
asked Aug 7 '19 at 17:18
Gilles 'SO- stop being evil'
37.6k7 gold badges101 silver badges166 bronze badges
0
votes
1answer
57 views
How to count all integers less than a given integer and having two contigous digits as $y$?
Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...
0
votes
0answers
13 views
Mapping every character to its next occurrence based on the number of unique characters between the occurrences
To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
2
votes
0answers
48 views
Edit distance between all word pairs
Let there be a dictionary of M words with average length N. We want to compute an M×M matrix of edit distances between all word pairs.
Since there are M² word pairs, and the pairwise edit distance ...
2
votes
1answer
232 views
Sorting an array of strings by length in linear complexity
I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity.
The max length of the strings is known.
Because of that, I tried using ...
2
votes
0answers
25 views
Permutation to maximise strings' common prefix
Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix.
Given a set $S=\{(s,w)\}$ of pairs of ...
0
votes
0answers
51 views
Suffix-automaton Largest common substring of multiple strings
Can anyone help with understanding how to solve "Largest common substring of multiple strings" problem with usage of Suffix-automaton?
I've found this a really good article about SA . But ...
3
votes
3answers
368 views
CFG for all strings of a’s and b’s that contain a different number of a’s and b’s
I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this:
S→A|B
A→aE|aA|EA
B→bE|bB|EB
E→aEbE|bEaE|Λ
...
1
vote
1answer
245 views
Suffix array and counting distinct substrings of specific length
I am trying to use the suffix array, and the LCP array to count all distinct substrings of a specified length.
I started with the algorithm for counting ALL distinct substrings. I solved it after ...
2
votes
1answer
38 views
Properties of reciprocal Quines
I was reading about the concept of quine and in particolar of "reciprocal Quines" for example a Program $A$ that output the code of a program $B$ and vice versa, with the two being written in the same ...
3
votes
2answers
1k views
Divide two strings to form palindrome
Given two strings, A and B, of the same length $n$, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.
I've ...
3
votes
1answer
298 views
Reductions between LIS and LCS
Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
0
votes
1answer
53 views
Non consant size alphabet
Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.
5
votes
0answers
61 views
Number of strings at given edit distance
I would like to know the number of strings at edit distance $n$ of a string $s$.
I guess this is textbook knowledge... but I cannot find the textbook in question.
More formally, I have an alphabet $\...
1
vote
0answers
33 views
Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?
A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply ...
7
votes
2answers
3k views
Longest common substring in linear time
We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity.
Can a solution be found in only linear time?
0
votes
0answers
349 views
Brute Force Approach for LCS and its Time Complexity
I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am ...
