Questions tagged [strings]
Questions about sequences of symbols, sets thereof and their properties as well as uses.
344
questions
2
votes
0answers
32 views
Edit distance between all word pairs
Let there be a dictionary of M words with average length N. We want to compute an M×M matrix of edit distances between all word pairs.
Since there are M² word pairs, and the pairwise edit distance ...
2
votes
1answer
46 views
Sorting an array of strings by length in linear complexity
I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity.
The max length of the strings is known.
Because of that, I tried using ...
2
votes
0answers
22 views
Permutation to maximise strings' common prefix
Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix.
Given a set $S=\{(s,w)\}$ of pairs of ...
0
votes
0answers
7 views
Suffix-automaton Largest common substring of multiple strings
Can anyone help with understanding how to solve "Largest common substring of multiple strings" problem with usage of Suffix-automaton?
I've found this a really good article about SA . But ...
3
votes
3answers
86 views
CFG for all strings of a’s and b’s that contain a different number of a’s and b’s
I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this:
S→A|B
A→aE|aA|EA
B→bE|bB|EB
E→aEbE|bEaE|Λ
...
1
vote
1answer
39 views
Suffix array and counting distinct substrings of specific length
I am trying to use the suffix array, and the LCP array to count all distinct substrings of a specified length.
I started with the algorithm for counting ALL distinct substrings. I solved it after ...
2
votes
1answer
34 views
Properties of reciprocal Quines
I was reading about the concept of quine and in particolar of "reciprocal Quines" for example a Program $A$ that output the code of a program $B$ and vice versa, with the two being written in the same ...
2
votes
2answers
109 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
59 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
38 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
45 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
28 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
1k 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
174 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
32 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
55 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
129 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
48 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
37 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
84 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
94 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
119 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
243 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
38 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
81 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
167 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
244 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
44 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
85 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
182 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
18 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
993 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
55 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
22 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
45 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
80 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
18 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
60 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
33 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
126 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
137 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
69 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
43 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 ...
