Skip to main content

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
0 answers
480 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 ...
PsychoKitten's user avatar
1 vote
0 answers
37 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 ...
user avatar
2 votes
1 answer
150 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 ...
Ewin Zuo's user avatar
0 votes
0 answers
64 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,...
2080's user avatar
  • 251
3 votes
1 answer
167 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}^...
spektr's user avatar
  • 453
0 votes
0 answers
127 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: ...
ved's user avatar
  • 101
0 votes
0 answers
44 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 ...
Suminda Sirinath S. Dharmasena's user avatar
0 votes
0 answers
27 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 ...
user avatar
1 vote
1 answer
126 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? ...
Kapa's user avatar
  • 137
1 vote
1 answer
40 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 ...
Arian B's user avatar
  • 13
1 vote
1 answer
26 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 ...
Lathan's user avatar
  • 23
0 votes
2 answers
92 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 ...
rzv09's user avatar
  • 13
1 vote
2 answers
105 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 ...
M.N.Raia's user avatar
  • 141
0 votes
1 answer
34 views

How do you prove these string/number radix encoding/decoding algorithms work?

A while back I learned of these great algorithms: ...
Lance's user avatar
  • 2,243
0 votes
1 answer
108 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 ...
Gareth Ma's user avatar
  • 103
1 vote
1 answer
282 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 ...
Giorgos Skourtsidis's user avatar
0 votes
2 answers
152 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 ...
Toothpick Anemone's user avatar
2 votes
1 answer
92 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 ...
MW Millar's user avatar
  • 123
1 vote
0 answers
70 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 $...
John's user avatar
  • 61
5 votes
1 answer
145 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 ...
Alex's user avatar
  • 171
2 votes
1 answer
151 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 ...
Nic's user avatar
  • 105
1 vote
1 answer
1k 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 ...
Abhishek Ghosh's user avatar
0 votes
2 answers
46 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 ...
Arjan's user avatar
  • 101
1 vote
0 answers
34 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 ...
MNael's user avatar
  • 111
0 votes
0 answers
91 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 - ...
Xenya Syrbulova's user avatar
1 vote
1 answer
299 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 ...
Sid's user avatar
  • 211
0 votes
0 answers
41 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)' ...
Márlon Ferreira's user avatar
2 votes
1 answer
78 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: ...
D3SL's user avatar
  • 23
1 vote
1 answer
155 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 ...
Ryan1729's user avatar
  • 364
1 vote
1 answer
462 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 ...
pblpbl's user avatar
  • 53
3 votes
0 answers
531 views

Should a prefix tree (trie) node store only a single character or a string?

I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters. Storing strings is for sure more space-efficient and ...
Martin Thoma's user avatar
  • 2,360
2 votes
1 answer
160 views

Given a list of strings, find every pair $(x,y)$ where $x$ is a subsequence of $y$. Possible to do better than $O(n^2)$?

Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a subsequence of $y$. We can assume all strings are of ...
securitymensch's user avatar
1 vote
0 answers
169 views

Fastest way to find a substring 'ab' inside a string 'abab'

Let $A$ be an input alphabet - a finite set of symbols. Elements of $A$ are called the characters. The alphabet I am interested in is the set of all ordinary letters ...
Alessandro Jacopson's user avatar
4 votes
3 answers
362 views

Sorting array of strings (with repetitions) according to a given ordering

We get two arrays: ordering = ["one", "two", "three"] and ...
Pe Wu's user avatar
  • 143
1 vote
1 answer
354 views

Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?

I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings. Example: Set 1: ...
Stalinko's user avatar
  • 143
3 votes
0 answers
42 views

Why does it take more than the original alphabet to generate sets of strings?

I am reading Computability by Nigel Cutland and I'm stumped on a brief statement about generating particular sets of strings that is not explained or given any examples. First, here are some ...
Jia Ming جيا ميڠ's user avatar
3 votes
1 answer
823 views

Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?

Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of ...
securitymensch's user avatar
0 votes
0 answers
29 views

Spliting strings into groups of similar strings

I would like to group a list of strings into groups of strings differing by max 1 character: For instance, given: [John, Alibaba, Johny, Alidaba, Mary] I would ...
dzieciou's user avatar
  • 175
4 votes
2 answers
267 views

How can you compute the expected edit distance in $O(2^{3n/2})$ time?

In a coding challenge an answer claimed to be able to compute the expected edit distance between two binary strings of length $n$ in $O(2^{3n/2})$ edit distance calculations by dynamic programming. A ...
Simd's user avatar
  • 996
7 votes
2 answers
364 views

How many operations of flipping all brackets on a substring of a string of brackets are needed to make the string 'correct'?

I call a string of brackets 'correct' if every opening bracket has a corresponding closing bracket somewhere after it and every closing bracket has a corresponding opening bracket somewhere before it. ...
Voso's user avatar
  • 73
2 votes
1 answer
144 views

Can I solve my decision problem in $O(n)$ time?

My algorithm solves a custom string problem but it loops twice making it $O(n^2)$ time. I'm asking here as I'm a beginner in self-learning algorithms. Decision Problem: Given an input list $A$, can ...
The T's user avatar
  • 321
0 votes
0 answers
91 views

Lexicographically minimal string rotation

In this page: https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation there is the Booth's Algorithm for lexicographically minimal string rotation but there is no proof. I can't access ...
asv's user avatar
  • 345
1 vote
0 answers
18 views

Finding fewest strings that cover $\Sigma^n$ up to $R$ edit operations

Let $\Sigma$ be the alphabet, $0<R<n$ be an integer and let $\Sigma^n$ denote the set of all strings of length $n$ over the alphabet. The task is to find the minimum $m$ such that there exist ...
Ameer Jewdaki's user avatar
5 votes
1 answer
118 views

Primitive word and cyclic rotations

Definition. A word $w \in \Sigma^*$ is primitive if $w=u^n \rightarrow n=1$. Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?
asv's user avatar
  • 345
1 vote
1 answer
253 views

How to construct a DFA which accepts all the strings endig with aa and no two consecutive b (bb)

I have to construct a DFA which ends with aa and does not contain any pair of b-s. A = {a,b}, {aa,baa,aaa,abaa,babaa,...}. I know how to construct them as separate DFAs but not together merged.
Maria's user avatar
  • 11
1 vote
1 answer
231 views

Find number of awesome substring of a given binary string

A binary string is given to us and we need to find number of awesome substring of that string .Definition of awesome string : A string is awesome if its length is divisible by number of 1's in it. ...
user avatar
3 votes
1 answer
70 views

Efficiently extendable hash function?

I'm wondering whether there exist any good hash functions with the following property: Assume that $x$ is some string over some alphabet $A$, then given $H(x)$ we can compute in $O(1)$ time both $H(ax)...
del's user avatar
  • 221
0 votes
0 answers
83 views

Inverse of Burrows-Wheeler

We can invert the Burrows-Wheeler with this method: The inverse can be understood this way. Take the final table in the BWT algorithm, and erase all but the last column. Given only this ...
asv's user avatar
  • 345
3 votes
1 answer
179 views

Does there exist a subset of substrings for reconstructing another string?

I am looking for a high performance algorithm to check whether I can reconstruct a given string using a given set of substrings. More details: Let's say our strings are over the alphabet $\Sigma$. ...
aminrd's user avatar
  • 499
6 votes
1 answer
2k views

Find the closest string to a fixed set of strings

I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the ...
spyr03's user avatar
  • 238

1 2
3
4 5
11