Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
429
questions
0
votes
1answer
7 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
12 views
Longest palindrome after swapping operation
I know that manachers algorith can be used to find longest palindromic substring of a string in linear time.
But I want to find the longest palindromic substring after swapping any two indices once.
...
0
votes
0answers
52 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
167 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
92 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' ...
-2
votes
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:
4
votes
1answer
59 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
52 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
45 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
39 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
34 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
15 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
53 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
17 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 ...
1
vote
2answers
116 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
91 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
56 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:
...
0
votes
0answers
15 views
Find optimal alignment between 2 strings with gap cost function
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:
Given two strings S1 and S2, find the ...
2
votes
1answer
158 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
43 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
49 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
22 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 ...
2
votes
1answer
54 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 ...
0
votes
0answers
18 views
Given start strings, find simplest DAG that constructs target strings by concatenation
Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,...
2
votes
1answer
44 views
Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$
Suppose we are given a language $\Sigma$ where, suppose, $|\Sigma| = O(1)$. Consider two fixed strings $A, B \in \Sigma^n$. Define the Hamming metric between these strings as
$$d_{H}(A,B) = \sum_{i=1}^...
0
votes
0answers
30 views
String membership in hash set time complexity
Given a string s and a hashset of strings words, what is the time complexity of the operation: ...
0
votes
0answers
12 views
What is the currently know fastest algorithms to convert each individual Java primitive and Number types to a Char Array/String
What is the currently know fastest algorithms to convert each individual Java primitive and Number types to a Char Array/String number representation while ...
0
votes
0answers
26 views
Filtering Messages
I saw this question posted and can't seem to find it for some reason, so I'm posting it again.
There's a leetcode problem that's asking for the number of possible strings that are alphabetically ...
1
vote
1answer
77 views
$\omega$-string avoiding a set of substrings
Given a set of strings $S$ over $\{a,b\}$. How to determine whether there is an infinite sequence consisting of ${a, b}$ (i.e., a $\omega$-string), which doesn't have any string in $S$ as a substring?
...
1
vote
1answer
20 views
which neural network is good for predecting the value of strings
I have a dataset that contains some strings. A numeric value is assigned to each string.
I want to develop a machine learning (deep learning) model to get a string and predict its value.
What neural ...
1
vote
1answer
22 views
In a set of sentences, how could I determine the fewest sentences that contains all characters?
So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced.
So ...
0
votes
2answers
22 views
string concatenation vs language concatenation
What exactly is the difference between
$$
C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}
$$
and
$$
D = \{a^nba^nba^nb | n \geq 0 \}
$$
It is known that D is non-regular and C is regular, but I am not sure ...
1
vote
2answers
45 views
A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?
First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS).
I) Vectors
A vector have a axiomatic ...
0
votes
1answer
26 views
How do you prove these string/number radix encoding/decoding algorithms work?
A while back I learned of these great algorithms:
...
0
votes
0answers
43 views
Finding first occurence of all possible matches?
Say you have multiple strings that you're trying to match in a text. And it's possible all these strings have a match in the text. Is there a good way to return out of all the matching strings the ...
0
votes
1answer
87 views
Binary string satisfying several constraints
I'm trying to solve this problem, but without success.
Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several ...
1
vote
1answer
87 views
Minimum number of given operations in order to group letters in a string
Description
Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be ...
0
votes
2answers
94 views
If we want to map abbreviations of full-English words (e.g. map “Jan” to “January”), how can we identify abbreviations which map to multiple words?
Short Version:
How can we construct a trie which maps abbreviations of names-of-the-month to full-month (we map the abbreviation "mar" to "march")?
The set of all abbreviations is ...
2
votes
1answer
64 views
Is there a way to determine whether a list of integers can be a prefix function?
Say you had
(0,0,0,1,2,3,4,5,6,7,8,9,10)
or
(0,1,0,1,0,1,2,3,0,1,0,0,1)
Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a ...
1
vote
0answers
56 views
Number of words of length n for special language
Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties:
if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
5
votes
1answer
58 views
Isn't this Commentz-Walter algorithm buggy?
I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible ...
3
votes
1answer
108 views
Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other
I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two ...
1
vote
1answer
196 views
Strings of infinite length?
Suddenly a thought came to my mind and I thought of resolving it as follows.
We know that:
String is a finite sequence of symbols from an alphabet $\Sigma$
i.e. we cannot have an infinite sequence ...
0
votes
2answers
35 views
Efficient way to concatenate strings to find specific split up values
I'm working with a list of objects ("Section") that contains a string value among other fields. The strings in all of the sections can be concatenated to form the complete text. I am, however, wanting ...
1
vote
0answers
31 views
What is the appropriate term for the “string splitting” problem?
To be clear, I didn't hear of this in any particular venue, and so can't point you to one.
Two variants that I can bring you:
String spitting
Given a string (sequence of elements), and a function ...
0
votes
0answers
28 views
Best way to find and store difference between two strings
I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - ...
1
vote
1answer
110 views
Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters)
You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern:
X1,X2,X3...Xn,Xn,...X3,X2,X1
where ...
0
votes
0answers
32 views
How would I make sure my compressed string has the smallest length possible?
I'm trying to make a function that takes a string and compresses the repeating blocks. The code I'm using is implemented in such a way that a single character like 'a' would be converted to '1(a)' ...
2
votes
1answer
34 views
Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?
Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong.
I have a puzzle: ...
1
vote
1answer
45 views
Are there search algorithms that perform better on a Rope than a String?
I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not ...
