Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
474
questions
0
votes
0
answers
4
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 ...
- 281
0
votes
0
answers
38
views
Construct Binary String Text based on Pattern Text for Worst Case of KMP Algorithm
Given a pattern binary string $P$ of length $m$, if $k$ is a given constant number, construct (provide algorithm/code in c, python) a text string $T$ (binary) of length $c\times m$, such that there is ...
- 281
1
vote
2
answers
53
views
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
Let $w$ and $x$ be two binary strings. Show that the Hamming distance of $wx$ and $xw$ cannot be 1.
I think one approach is a proof by contradiction. I was thinking of explicitly writing out $w = w_1\...
- 225
0
votes
1
answer
53
views
Time Complexity for the given algorithm
Recently, I had to implement the following algorithm (similarly). Code in Kotlin:
...
- 101
1
vote
0
answers
22
views
What are practical applications for markovs algorithm(string rewriting systems)
:)
Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
- 11
0
votes
1
answer
53
views
Given a list of strings enumerated over a finite alphabet, what's the most efficient way to get a string by its index?
Say you have the finite alphabet $\{a,b,c,d,e,f,g\}$ and an enumeration of finite strings over it by the shortlex order (length-lexicographic ordering), starting with the empty string, i.e.,
$\epsilon,...
- 1
1
vote
1
answer
38
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 ...
- 165
1
vote
1
answer
31
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 ...
- 11
2
votes
2
answers
49
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
0
votes
1
answer
58
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
1
vote
1
answer
46
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 ...
- 31
2
votes
1
answer
26
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}...
- 123
1
vote
4
answers
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 ...
- 287
6
votes
1
answer
92
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 ...
- 181
1
vote
0
answers
26
views
What is the name of the following problem on sets of strings
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, ...
0
votes
2
answers
98
views
Does creating a deep copy of a string of size N (in python) take space complexity O(N) or O(1)?
My question comes from solving this LeetCode question, in which we are given a string of characters with size N, and one of the solutions is to use a hashmap (dictionary in Python) to count the ...
- 113
1
vote
2
answers
43
views
Polynomial algorithm for the «Input Series» Problem
Can you help me design an algorithm to solve the following problem in polynomial time?
Let n be a given natural number. We define an input series of length n to be a string of length n which is built ...
- 61
0
votes
0
answers
8
views
Text macros(replacements) based on pre-defined rules
I'm writing a web app that requires a component that let's the user input a piece of text thats automatically formatted based on something the client calls "macros". These macros have a very ...
6
votes
1
answer
109
views
Find all n bit numbers with k ones and unique under circular shift
I am trying to traverse through all uint64_t with k 1s. Then I find that if x and y are circular shifts of each other, they will output the same result. So I'm trying to optimize my code.
The problem ...
- 61
0
votes
0
answers
23
views
If string x is conjugate to string y, how can you prove that the reverse of x is conjugate to the reverse of y?
I am relatively new to writing proofs and I am stuck trying to prove that if $x$ ~ $y$, then $x^R$ ~ $y^R$. Any help would be appreciated!
0
votes
0
answers
44
views
Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?
In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state:
The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
- 1,871
0
votes
0
answers
37
views
Permutation of a valid bracketing
Given a permutation $\pi$ of length $2n$, how can we find a valid bracketing (balanced string of opening and closing parentheses) which will remain valid when permuted under $\pi$?
For example, for $\...
- 31
1
vote
1
answer
43
views
Quicksort for Strings
I am currently trying to study the Quicksort algorithm. I understand how it works for integers but can anyone explain how does Quicksort algorithm work with strings?
The reason for my confusion is ...
1
vote
2
answers
116
views
Prove my algorithm that solves ABC String problem in Codeforces is correct
Here's the statements of problem A, "ABC String" in Educational Codeforces Round 105 (Rated for Div. 2)
You are given a string a, consisting of n characters, n is even.
For each i from 1 to ...
0
votes
1
answer
35
views
Empty string in an ambiguous grammar?
I'm a bit confused by the role of the empty string in this ambiguous grammar:
A' -> A
A -> if A B
A -> null
B -> [empty string]
B -> else S
So what ...
- 101
1
vote
0
answers
45
views
Check if string contains pattern (with respect to one-to-one symbols mapping) [closed]
I'm trying to solve following problem:
Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original ...
-1
votes
1
answer
454
views
Dynamic programming to find number of ways to divide string into primes
I am studying for final algorithms exam and saw this question:
Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers >= 2....
- 1
0
votes
0
answers
32
views
An idempotent grammar for text decoding?
I'd like to create a function decode(x : string) such that decode(x : string) == decode(decode(x : string)).
I believe I can ...
- 113
1
vote
0
answers
30
views
Longest substring creating palindromic substring in other string
Given two strings $s, t$, I would liketo find a maximal subsequence of $t$ (denoted as $t'$), such that the concatenation of $t'$ with its reverse ($t'_R$), is a palindromic substring of $s$.
I ...
- 111
0
votes
0
answers
25
views
Finding matches between an input string and a fixed set of strings
I need to compare an input string to multiple strings which I'll refer to as fixed strings, and you can assume the latter won't change. Comparison disregards letters with special characters, only ...
- 158
0
votes
0
answers
24
views
using TRIE for strings?
I saw the following question online:
Init - Initlize data structure in O(1).
Insert(s) - Add string s to your Data Structure in ...
- 1
13
votes
5
answers
5k
views
How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?
I understand the textbook explanation of how to use dynamic programming to find the minimum edit distance between 2 strings but how do we get to pick the 2nd string?
I don't think the entire ...
- 659
6
votes
1
answer
176
views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
- 63
0
votes
0
answers
44
views
Number of borders of all substrings in a string
Can you please help with solving the following problem. Given a string $s$, we need to find the number of borders of all its substrings. For a single string we can count all the borders in O(n) time ...
- 49
-1
votes
1
answer
64
views
Proving correctness for greedy algorithm in string removal problem
Problem Statement:
You are given a string s and two integers x and y. You can perform two types of operations any number of times.
Remove substring "ab" and gain x points.
For example, when ...
- 39
-1
votes
1
answer
82
views
High Level description of Turing Machines
How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
2
votes
1
answer
48
views
Given a finite alphabet, how to generate all possible strings while excluding those that don't feature an element at least once?
Say you have the finite alphabet {a,b,c,d,e,f,g}. It's trivial to enumerate all strings of length <= 1000 over that set.
But what would be an efficient way of specifying a subset of those strings ...
- 23
0
votes
0
answers
94
views
Fast text comparison algorithm for long texts
I want to calculate a similarity ratio between two long texts (by "long", I imply something around 1000 characters or higher). For example, two texts with only one word changing should have ...
1
vote
1
answer
69
views
Counting substrings of a string that do not contain a given string
Let's say we have a string $s[0..n-1]$ and a pattern $p[0..m-1]$ with $m < n$. I am looking for an $O(nm)$ solution to the following problem: find the number of substrings of $s$ not containing $p$ ...
- 49
2
votes
1
answer
48
views
How can I prove that the empty string is the identity element with regards to the operation of concatenation?
Let $w$ be a string over an alphabet $\Sigma$. It is obvious that $w \circ \epsilon = \epsilon \circ w = w$.
However I'm having a hard time coming up with a proof for that (which I assume should be ...
- 123
3
votes
1
answer
155
views
Sum of squares of length of longest common prefix for all pairs in given strings
Given a list of unique strings, how can I find the sum of squares of longest common prefixes length for all pairs?
I think a trie will be useful but I'm not sure how to calculate the final result.
For ...
- 131
4
votes
1
answer
110
views
please help me understand the algorithm for building the KMP failure function
I am struggling to grasp the algorithm for building the KMP failure function. The bulk of what is making my understanding incomplete concerns the line ...
- 39
0
votes
1
answer
184
views
What is the optimal solution for the following "Largest lexicographical string with <= K consecutive elements" problem? Why is my answer wrong?
This is a simple question I ran into in a remote interview:
Given a collection of letters, permute them (or one of its subset) into a string such that:
each letter can only be repeated for <= 11 ...
- 101
2
votes
1
answer
145
views
Z-function and the minimum string period
Let $s$ be a string of length $n$. One of the classical solutions to the problem of finding the smallest period $p$ of $s$ (that is, smallest $p$ such that $s$ can be obtained as a concatenation of ...
- 49
3
votes
0
answers
119
views
Remove a subsequence from a string and append it at the end
Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
- 31
0
votes
1
answer
46
views
List the lengths of all the prefix-suffixes in $O(n^{1+\epsilon})$ time
A proper prefix of a string $s$ that is also equal to a suffix of $s$ is called a PS (prefix-suffix).
Given a string $s$ of length $n$ is there an algorithm listing the lengths of all the PSs in $O(n^{...
- 1
2
votes
1
answer
128
views
Number of subsequence with k distinct characters
"A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order."
Suppose we have string s="aabca&...
- 31
2
votes
1
answer
27
views
Proving $S=SL\implies S=\emptyset$
Let $L\subseteq \Sigma^*$ such that $\{\epsilon\}\not\in L$. Then for any $S\subseteq \Sigma^*,
S=SL\implies S=\emptyset$.
So we suppose $S=SL$ and $S\ne\emptyset$. Then $\exists w\in S$ such that $...
- 169
0
votes
0
answers
49
views
How to find the LCP of string pairs in a set
I have a set of $k$ strings of $n$ length each. I need an algorithmic strategy that finds the LCP (Longest Common Prefix) of each set's string pair. In addition, I need time complexity $O(k*n+a)$, ...
- 113
0
votes
1
answer
32
views
Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)
If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because ...
- 15