Questions tagged [strings]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
26 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 ...
0
votes
1answer
157 views

String Search - how to find the "most" accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
-1
votes
1answer
100 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
vote
2answers
50 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
23 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
41 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 ...
23
votes
1answer
1k views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
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 ...
0
votes
0answers
30 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 ...
6
votes
1answer
130 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 ...
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 ...
6
votes
0answers
148 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. ...
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 ...
4
votes
2answers
855 views

Count the unique subsequences

I'm trying to count the number of subsequences of a long string. e.g. BANANA -> B, A, N, BA, BN, AA, NN, NA, BAN, BAA, BNA, BNN, ANA, AAA, NAN, NNA, etc There's the horribly inefficient way, which ...
1
vote
1answer
134 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 ...
8
votes
2answers
1k views

Count of distinct substrings in string inside range

Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ ...
2
votes
1answer
4k views

Convert given string to Palindrome with given substring

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other ...
0
votes
0answers
33 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 ...
0
votes
1answer
239 views

Finding longest prefix of a given string in set of strings that satisies some property

I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find ...
-1
votes
1answer
32 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
vote
1answer
209 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 ...
4
votes
1answer
72 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}...
-1
votes
1answer
46 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
36 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
38 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
47 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
45 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
49 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
162 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
60 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
82 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
35 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
70 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 $...
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
28 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
28 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 ...
0
votes
0answers
109 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 -...
2
votes
1answer
65 views

Why is KMP preprocessing O(N)?

My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from ...
2
votes
1answer
169 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' ...
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
143 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
270 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
99 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
2 3 4 5
10