Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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....