# Questions tagged [strings]

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

455 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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....
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
72 views

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&...
25 views

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 $... 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 ... 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)$, ... 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 ... 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 -... 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 ... 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' ... 1answer 34 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: 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). ... 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. ... 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$...
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 ...