Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
2
votes
2answers
64 views
Divide two strings to form palindrome
Given two strings, A and B, of the same length $n$, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.
I've ...
3
votes
1answer
49 views
Reductions between LIS and LCS
Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
0
votes
1answer
34 views
Non consant size alphabet
Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.
5
votes
0answers
44 views
Number of strings at given edit distance
I would like to know the number of strings at edit distance $n$ of a string $s$.
I guess this is textbook knowledge... but I cannot find the textbook in question.
More formally, I have an alphabet $\...
1
vote
0answers
27 views
Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?
A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply ...
7
votes
2answers
919 views
Longest common substring in linear time
We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity.
Can a solution be found in only linear time?
0
votes
0answers
131 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
27 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
53 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
104 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
46 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
35 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
38 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
81 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
76 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
104 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
135 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
48 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
36 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
76 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
111 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
164 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
33 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
72 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
179 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
17 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 ...
2
votes
1answer
876 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
21 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
54 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
21 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
44 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
40 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
60 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\}$.
1
vote
1answer
78 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
54 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
49 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
123 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
135 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
66 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
41 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
388 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
109 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
118 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
335 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
360 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
17 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 ...
