Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
454
questions
0
votes
0answers
35 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 $\...
1
vote
1answer
33 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
2answers
62 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
1answer
26 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 ...
1
vote
0answers
42 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
1answer
129 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....
0
votes
0answers
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 ...
1
vote
0answers
29 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 ...
0
votes
0answers
23 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 ...
0
votes
0answers
23 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 ...
12
votes
5answers
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 ...
6
votes
1answer
169 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.
...
0
votes
0answers
36 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 ...
-1
votes
1answer
34 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 ...
-1
votes
1answer
57 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
1answer
37 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 ...
0
votes
0answers
47 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
1answer
53 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$ ...
2
votes
1answer
39 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 ...
3
votes
1answer
49 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 ...
4
votes
1answer
53 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 ...
0
votes
1answer
170 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 ...
1
vote
1answer
73 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 ...
0
votes
0answers
20 views
question about common prefix of Strings
we are given n Strings of total Length K and also we have m queries about these strings.
each query, contains 2 index ( for example a , b ) and then we should calculate the length of longest common ...
3
votes
0answers
97 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 ...
0
votes
1answer
40 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^{...
2
votes
1answer
95 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&...
2
votes
1answer
25 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 $...
0
votes
0answers
34 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)$, ...
0
votes
1answer
30 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 ...
1
vote
0answers
48 views
Longest palindrome after swapping operation
I know that Manacher's algorithm can be used to find the longest palindromic substring of a string in linear time.
But I want to find the longest palindromic substring after swapping any two indices ...
0
votes
0answers
110 views
Can a Turing machine start on a blank?
Couldn't find a definitive answer anywhere so asking here. I have a Turing machine and the start state can go straight to the end state without passing through any of the other five states via
Blank -...
1
vote
1answer
214 views
calculating the string similarity of an optimal alignment
description of the algorithms behavior
I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
2
votes
1answer
177 views
Number of substrings possible with even characters
Consider a string 'ABBAA'
Possible substrings with even number of characters are $4$
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even - ($0$)
Similarly 'BB' ...
-1
votes
1answer
35 views
Find the most frequent alphabet appearing in the given string. In case letter with same frequency, choose the one which comes first alphabetically
This is the desired result which I want:
4
votes
1answer
79 views
Las Vegas algorithm for finding 00000 in bit string
Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). ...
0
votes
1answer
149 views
Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$
Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$.
This is exercise 6 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. ...
1
vote
1answer
285 views
Prove that $(uv)^R = v^Ru^R$
The reverse of a string, introduced informally above, can be defined more precisely by the recursive rules $$a^R=a,$$ $$(wa)^R=aw^R,$$ for all $a \in \Sigma$, $w \in \Sigma^*$. Use this to prove that $...
0
votes
2answers
103 views
Find the maximum number of contiguous occurrences of smaller string s in a larger string l
Say we have two strings s and l, and they only have characters 'a' through 'z' (lowercase English alphabet characters). The task is to find the maximum number of consecutive occurrences of s in l.
Ex.
...
1
vote
1answer
37 views
Families of sets indexed by another set
I am reading Automata and Computability by Dexter C. Kozen and I am in the first chapter entitled Strings and Sets.
If we have a set $A=\{ab,b\}$ do we get to assume that the null string $\epsilon$ is ...
1
vote
1answer
20 views
Sorting in computing longest increasing subsequence
I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman.
I'm struggling to understand parts of the proof of Theorem 3.5,
especially this bit:
...
1
vote
1answer
105 views
Can't wrap my head around on building a suffix table for Boyer Moore
My resources were the following video, as well as this video.
Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following:
k
suffix
d2
1
...
0
votes
1answer
24 views
Replacement of a substring with another substring in a string
I apologize if this is not the right stackexchange for this question. I was playing around with the Python programming language, when I discovered something strange. It concerns replacing a substring ...
2
votes
2answers
235 views
What is the simplest algorithm to compress a string?
I need to compress a string in my application but I am very limited in the operations I can perform. In particular, I cannot store data in any file and I cannot query any database. Also, I cannot call ...
1
vote
2answers
140 views
Time complexity of comparing $N$ strings
I would like to double check myself.
As I understand time complexity of comparing two strings in the worst case is $O(n)$, where $n$ is the length of the strings (let's say they are equal length).
In ...
1
vote
1answer
60 views
Is string spliting formally defined when the string delimiter is an empty string?
Depending on the API/language you use, splitting the string "ABCD" using "" as a delimiter gets you:
...
2
votes
1answer
198 views
Find optimal local alignment of two strings with restrictions
I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.
The problem:
We want to find an optimal local ...
2
votes
1answer
54 views
What is the SetHorspool string searching algorithm and how is it implemented?
What is the SetHorspool string searching algorithm with pseudo-code so it can be easily implemented in a language of choice?
This has been implemented in 2 libraries I have come across:
https://app-...
1
vote
0answers
128 views
Boyer-Moore jump table
I have a pattern $P$ of length $m$, i.e. $P = p_0, p_1, \ldots, p_{m-1}$
which I want to build a simple jump table for (not considering special optimizing cases for now).
I only want to build a jump ...
0
votes
0answers
23 views
How many strings of length |w| are unrelated?
For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated?
A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically ...