Questions tagged [strings]

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

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
0 votes
1 answer
53 views

Time Complexity for the given algorithm

Recently, I had to implement the following algorithm (similarly). Code in Kotlin: ...
user avatar
  • 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 ...
user avatar
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,...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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: $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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}...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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!
user avatar
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 ...
user avatar
  • 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 $\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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....
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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^{...
user avatar
  • 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&...
user avatar
  • 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 $...
user avatar
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)$, ...
user avatar
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 ...
user avatar

1
2 3 4 5
10