Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
0
votes
0answers
39 views
Brute Force Approach for LCS and its Time Complexity
I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am ...
2
votes
2answers
22 views
O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?
Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem.
If
s = little string and S = len(s)
b = big string and ...
3
votes
1answer
51 views
Find the smallest set of strings which “covers” a given set of strings (coverage = containing as substring)
Let $S$ be a finite set of strings and $0 < k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds:
$\forall t \in T(k,l): k \leq |t| \leq l$
$\...
2
votes
1answer
65 views
What is an efficient data structure for prefix matching?
I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 ...
1
vote
1answer
45 views
Let u and v be two strings. What about the reverse order of their concatenaited string?
let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$?
Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.
0
votes
0answers
32 views
Returning all the combinations of a string using regex
Is it possible for a regex pattern to return all the 2^n combinations of characters of a string as matches?
For example, if the string is ...
4
votes
0answers
35 views
Highest covering repeated string
Let's say I have the following string:
XXXXXAYYYYBYYYYCXXXXXDYYYY
We can see that the substring XXXXX is 5 characters long, ...
3
votes
1answer
78 views
Replace queries on string
Let's define a replace query on some string $s$.
Consider a string $s$ of length $n$ over alphabet $C = \{ c_{0}, c_{1}, c_{2}, \dots, c_{k}\}$. Also consider $l, r \in \{0, 1, 2, \dots, n - 1\}, l \...
1
vote
0answers
35 views
Algorithm for DFA accepting any string with ending with a particular substring
Is there any possible general algorithm for constructing a DFA such that it accepts any string, which has a given sub-string in the suffix(end) for any given language. The algorithm should directly ...
-1
votes
1answer
82 views
Find the Most Frequent Ordered Word Pair In a Document
This is a problem from Skiena's excellent book The Algorithm Design Manual:
Give an algorithm for finding an ordered word pair(e.g."New York")
occurring with the greatest frequency in a given ...
0
votes
1answer
33 views
Large-scale string clustering
I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at ...
1
vote
1answer
46 views
Grammar of words with exactly $k$ prefixes in another grammar
Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that
$$ L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\} $$
where $\text{Pref}(w)$ is the set ...
0
votes
0answers
32 views
use sparse table to optimising queries in suffix array
I want to build a suffix array and handle these queries:
1.word search in a text
2.longest common prefix of two suffixes(LCP)
so after making the suffix array,I want to do these requests by ...
1
vote
2answers
72 views
Why does little endian apply to numbers and not to text strings?
The Portable Executable file format is the format that Windows EXE files use.
It is a binary format.
Numbers are in little endian form. Thus, the following hex represents the decimal number 256, not ...
0
votes
0answers
72 views
Shortest Uncommon Subsequence
Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings?
For example,
Input : S = “babab” T = “babba”
Output : 3The subsequence “aab” of ...
1
vote
1answer
97 views
Word ladder problem for words with different length
Is there some one who know any algorithm for word ladder problem with words of different length?
Actually we have some strings with same length and some strings with one length longer but not from ...
0
votes
0answers
27 views
How use generalized suffix tree to match prefix string?
I know that generalized suffix tree can match substring for a given pattern.
But I have need a data structure which is able to
match prefix of many strings.
match sub string of of many strings.
For ...
0
votes
1answer
41 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 ...
3
votes
1answer
175 views
Longest substrings of common length with the same parity
Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions:
length of both $A$ and $B$ is equal to $x$;
sum of ...
2
votes
1answer
16 views
Approximating unique string occurrences using a small, fixed amount of memory
Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track ...
3
votes
1answer
344 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 ...
1
vote
1answer
20 views
Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered
I am not well versed in this topic so please pardon any ambiguous notation.
I am trying to describe the language of this grammar in set-theoretic notation.
The Grammar is given by:
$ S \rightarrow ...
1
vote
1answer
47 views
Designing a context free grammar for a language; When to use the empty string
$L= \{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \{a,b\}^*\}$ over the alphabet $\Sigma = \{a,b,c\}$
How can a grammar be created from the language without the use of the empty string. Below is my ...
1
vote
1answer
20 views
A hangman variation: determining a string by guessing substrings contained in it
I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I ...
2
votes
1answer
39 views
longest sub-sequence in both directions
Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.
Example: A = cabca
the sub-sequence S = abc is the ...
2
votes
1answer
39 views
Uniqueness of byte arrays
Consider the situation, when you're given M byte arrays of size N, and you need to check if all of them have unique content (so ...
1
vote
1answer
59 views
Find the number of strings in the language $(∅∅^∗ + ∅)$
Consider the language $L = \emptyset\emptyset^∗ + \emptyset$.
How many words does $L$ contain? Zero or one?
Note: $\emptyset^∗ =\{\epsilon\}$.
0
votes
1answer
66 views
Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?
The Problem:
I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set:
...
1
vote
0answers
17 views
Estimated vs actual period in Two-Way string search
Both the original paper and all implementations I've seen of the Two Way string search algorithm estimate the period of the needle as $\max(|u|,|v|)$+1 (where $u$ and $v$ are the critical factors). ...
2
votes
1answer
45 views
Regular expression for capturing a “C-style” string
I have started to learn automata theory and languages. I am new to regular expressions.
As a use case in real world, I would like to construct a regular expression to accept a c-style string: ...
1
vote
0answers
32 views
Detect all distinct k-th powers in a string for all k ≥ 3
In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$.
The ...
2
votes
1answer
46 views
How does topic or tag suggestion algorithms work?
I know it's a keyword based search. But sites like Quora have some good suggesting algorithms where the algorithm understands the intent of question asked rather than just the keywords meanings.
For ...
5
votes
1answer
111 views
Permutation of words that have matched parentheses
Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem:
Input: words $x_1,\dots,x_n \in \Sigma^*$
Question: does there exist a ...
2
votes
1answer
129 views
Finding the maximum substring for which a given predicate is true
Given a string $S$ of length $N$ and a string predicate $F$, find the maximum substring, $s$, such that $F(s) = \text{true}$. Assume that $F$ satisfies the following:
If $F(g) = \text{true}$, then ...
2
votes
1answer
57 views
String matching
I need to design a data structure to which I can efficiently add new words(Strings) and search for an existing word. Also, the search word can contain . in it which ...
2
votes
1answer
37 views
Minimum number of strings to cover entire space within Hamming distance
Given $(n, k)$:
What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string?
Is there an asymptotic expansion or lower ...
2
votes
1answer
31 views
optimize string search on black-box function
Given a lower-bound predicate function which returns true if an input is greater than or equal to a constant string, what is the optimal way to search for the ...
1
vote
0answers
25 views
Reference request: Practical string algorithms
I think I have quite a good understanding of string algorithms. However, a couple of days ago, I came across this post: Find all pairs of strings in a set with Levenshtein distance < d
I was ...
3
votes
1answer
281 views
Merge a set of strings based on overlaps
I have a set of strings that are slices of a single, longer string. It is not guaranteed, however, that any two strings from this set must overlap: only that all of them together overlap. I want to ...
1
vote
1answer
95 views
Construct binary palindrome by repeated appending and trimming
I was reading an article on Construct binary palindrome by repeated appending and trimming. The problem is Given n and k, Construct a palindrome of size n using a binary number of size k repeating ...
5
votes
0answers
115 views
Partitioning through block moves to the end
Suppose we have a binary string $s$. We wish to partition this string in a series of $0$s followed by $1$s (alternatively: we wish to sort), using only one operation: moving three consecutive elements ...
0
votes
1answer
240 views
Complexity of Longest Palindromic Subsequence Algorithm
I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches:
Recursive Algoritm
Dynamic Programming
Dynamic programming should be the better option in this ...
1
vote
1answer
257 views
Longest repeated substring
I am trying to solve a problem- Longest repeated substring in a string. Firstly, I built a suffix tree that takes O(n) time and then I traversed the suffix tree to find the deepest internal node. I am ...
1
vote
0answers
16 views
Pseudo-random regex-searchable function
Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties:
$f$ is efficiently ...
2
votes
0answers
49 views
Minimization of simple cyclic automata
Version 1 of the question: I am looking for any correct $O(n)$ algorithm in the literature which will solve the DFA minimization problem referred to in the quote below from [Almeida & Zeitoun 2008]...
0
votes
0answers
45 views
Variable bytes (bit arrays) and flipping single bits?
My interest is strictly theoretical at this point, but ultimately applied.
Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ...
2
votes
0answers
32 views
Bad character rule in the Apostolico–Giancarlo algorithm
In the paper "Tight bounds on the complexity of the Apostoliko-Giancarlo algorithm" by Crochemore and Lecroq authors prove that algorithm performs not more than $1.5n$ comparison of characters in the ...
5
votes
1answer
406 views
Find all substrings that fit the mask with asterisks
There is a problem.
Given string $text$ containing only letters and string $mask$ containing letters and asterisks (*), where asterisk means substitution of zero or more letters, find all substrings ...
3
votes
1answer
93 views
Can ropes (AVL trees) be interned?
Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time?
I recently implemented a rope ...
2
votes
1answer
35 views
Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods
When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40.
Reference:
Here's a reference: https://en....
