Stack Exchange Network

Stack Exchange network consists of 174 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 about sequences of symbols, sets thereof and their properties as well as uses.

3
votes
1answer
130 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
13 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 ...
1
vote
1answer
41 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
17 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
32 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 ...
0
votes
1answer
10 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
30 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
38 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
53 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
53 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
16 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
28 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: ...
0
votes
0answers
29 views

Text alignment algorithm for word misspelling and rearrangement

I'm working on a project involving OCR, and I'm writing a post-processor using which the user corrects the OCR output using a text editor. The OCR algorithm returns a list of "Detected Words", each ...
1
vote
0answers
30 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 ...
0
votes
0answers
13 views

Definition of string-generation for NFAs

I am new to automaton theory, and I am currently trying to think my way through the basic concepts. Since I come from a linguistics perspective, I find it helpful to think of automatons as string-...
2
votes
1answer
43 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
78 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 ...
0
votes
0answers
27 views

Convert arbitrary length String representing a decimal number to another base

Hopefully this question is fairly straight forward. I need to convert a String representing a decimal number to another base 2^16. I have a way to store very large numbers and perform arithmetic on ...
2
votes
1answer
92 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
49 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
23 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
28 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
57 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
60 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
112 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
115 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
115 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
15 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
30 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
38 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
27 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
377 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
68 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
32 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....
0
votes
1answer
26 views

Test a bit substring function

How do we test the following function? bits(bitstring, i, j) which returns a copy of the substring from i to ...
3
votes
2answers
196 views

Count the unique subsequences

I'm trying to count the number of subsequences of a long string. e.g. BANANA -> B, A, N, BA, BN, AA, NN, NA, BAN, BAA, BNA, BNN, ANA, AAA, NAN, NNA, etc There's the horribly inefficient way, which ...
3
votes
1answer
72 views

Shortest Non-Subsequence String With Constant-Size Alphabet

Let $S[1..n] \in \Sigma^*$ be a string of $n$ symbols over the alphabet $\Sigma$ where $|\Sigma| \in \mathcal{O}(1)$. Determine a shortest string which cannot be obtained from $S$ by deleting some (...
1
vote
1answer
76 views

Filling a string with wildcards with minimum cost

You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string. You are allowed to write data to the string in blocks of ...
1
vote
1answer
135 views

The set of all eventually periodic words is not Buchi Recognizable?

An $\omega$-word $s \in \Sigma^\omega$ is eventually periodic if it is of the form $s = uv^\omega$ for finite words $u, v \in \Sigma^*$. I want to show that the set of all eventually periodic words ...
4
votes
1answer
194 views

Finding the smallest string that contains a given set of substrings

The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible....
1
vote
1answer
39 views

Computing 'score' of string which preserves < relation

Is there a way to calculate some kind of numerical 'score' for arbitrary strings which when compared with score of some other string will preserve '<' relation? I've searched for order preserving ...
-1
votes
1answer
16 views

Time Complexity of reconstructing corrupted file

Suppose all the spaces between the words(only small letter alphabets and no punctuation) in a file has been deleted and we need to reconstruct the file. There is a dictionary available which answers ...
0
votes
0answers
29 views

Suffix Trie with indexes of the last substring

As I understood there is a algorithm ("black box") that build trie from a string by O(n) time complexity, This algorithm use pointer to the first appearance of the substring in the string. Is the a ...
1
vote
2answers
52 views

Finding common structure in strings

I don't even know the right words to describe my problem, so I'll start with an example: "aabaa", "ccrcc", "ffaff" are equivalent to some extent, because they all have the same length and follow the ...
0
votes
0answers
21 views

the question from this paper : Infinitary Equilibrium Logic and Strongly Equivalent Logic Programs

In the paper "Infinitary Equilibrium Logic and Strongly Equivalent Logic Programs", the authors claim: The effect of adding (1) to a logic program describing $p$ and $q$ is, in general, not the ...
0
votes
2answers
369 views

Smallest length such that all substrings of that length contain at least 1 common character

Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common ...
1
vote
1answer
131 views

return all strings contains given string in suffix tree

Here is my question: Given a compressed suffix tree of string S and a substring T. I need to return all substrings of S that begins with the substring T sorted by lexicographic order. My approach: I ...
0
votes
1answer
33 views

If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?

If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971). By the definition of non deterministic ...
-1
votes
1answer
67 views

Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)

I read The Complexity of Theorem-Proving Procedures by Stephen A. Cook (1971). Cook explains how to create a boolean formula $\Phi$ from $(M,w)$, where $M$ is a non-deterministic Turing machine that ...