Questions about sequences of symbols, sets thereof and their properties as well as uses.

learn more… | top users | synonyms

2
votes
3answers
48 views

Is there a standard (common) notation for the following operation on binary strings?

Typically, we use the notation $S = \{0, 1\}^n$ to denote the set of all $n$-bit strings. Suppose that I wanted to extract a subset of the strings where certain bits have some fixed values. For ...
2
votes
2answers
132 views

Time complexity of a problem inspired by palindromes

This was inspired by Bradshaw's question originally posted on Math.SatckExchange. EVEN PALINDROME: Input: Given a list of strings $[v_i, v_2, ... ,v_n]$ where $\Sigma |v_i| $ is even number. ...
1
vote
0answers
29 views

Counting the number of non-overlapping squares and cubes in a string

Given a string S of length n that contains exactly $\lceil\frac{n}{3}\rceil$ b's and $\lceil\frac{2n}{3}\rceil$ a's: Suppose the charge is 2 for each non-overlapping occurrence of aaa, and 1 for each ...
0
votes
1answer
23 views

Levenshtein distance cabable working with (large) vectors - not strings

Long version: Is there any algorithm similar to Levenshtein distance which can compare vectors? I will post several examples with desired inputs/outputs and then I will also show that it is not the ...
2
votes
1answer
15 views

Transitivity of concat comparison

I am trying to solve the problem of finding the permutation, amongst all possible ones, of an array of strings, where the concatenation of them compares smallest lexicographically. I solve it with an ...
0
votes
2answers
54 views

Longest substring with consecutive repetitions

I want to find the longest substring which is repeated without any gap between the repetitions. That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring ...
3
votes
0answers
30 views

Using Jaro-Winkler similarity to recognize matching strings

How do I use the Jaro-Winkler similarity measure to test whether two strings should be considered to match each other? I tried comparing the Jaro-Winkler score to a fixed threshold: e.g., if the ...
0
votes
1answer
36 views

Turing Machines: decidability and bounds checking

I am wanting to show that it is decidable that a Turing machine M, on input w, ever attempts to move its head past the right end of the input string w. I'm assuming I construct a TM which shifts the ...
0
votes
1answer
46 views

representing set of non-overlaping string in formal notation

I want to represent a set of any substrings which come from an original string with constraint that all substrings should not be overlapped. To be more clear please consider the example below: e.g. ...
1
vote
1answer
86 views

Minimum length of string using chars appearing in a given string but not a substring of that string

Suppose we're given a string like "aabaccbbca", and want to find a short string that's not a substring of this string. However, we're limited to using the ...
1
vote
1answer
86 views

How to find longest recurring pattern from lage string data set?

I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example ...
4
votes
1answer
40 views

How do I show that an equivalence class of a language containing an empty string is infinite

The question is as follows: Let $L$ be a language (not necessarily regular) over an alphabet. Show that if the equivalence class containing the empty string $[ \epsilon ]$ is not $\{ \epsilon ...
-4
votes
1answer
45 views

How do you call this typical file name order? [closed]

log1.gz log10.gz log100.gz log101.gz log102.gz log103.gz
1
vote
1answer
34 views

Inplace sorting of variable length records

Is there an in-place algorithm for sorting variable length records? For example a vector of arbitrary length strings. Most provided in-place algorithms assume that you can switch two elements ...
1
vote
1answer
31 views

How many segmentations are possible for a string length N?

I have a string with length N. I would like to know how many segmentations are possible to it. Consider the example abcdc the number of N = 5 All possible ...
2
votes
0answers
164 views

Efficient algorithm to approximate membership in a set of strings

I devised an algorithm / data structure and I would like to ask whether it already exists. The problem statement is: after having added some number of strings to the set, determine whether a given ...
3
votes
2answers
81 views

Which is the proper algorithm to figure repeated substrings of longest total length?

Given a string $S$ and a substring $T$, define the value of $T$ to be the total length (in characters) of all non-overlapping instances of $T$ in $S$. In other words, the value of $T$ is the length ...
2
votes
2answers
49 views

Storage cost of a suffix array

MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size ...
5
votes
2answers
75 views

Finding the number of square prefixes of a string in linear time

Let square denote a concatenation of two identical, nonempty strings. Given a string $w$, devise an $O(|w|)$ algorithm that counts the number of prefixes of $w$ that are squares. My initial ...
3
votes
1answer
99 views

Find all pairs of strings in a set with Levenshtein distance < d

I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that ...
1
vote
1answer
44 views

How is n-gram different from k-mer?

How is n-gram different from k-mer? Both seem to be (n or k) length substrings of a larger string. Are these just terms common with different practitioners? viz. Computer Scientists and ...
0
votes
1answer
24 views

Question about DFA for exact string matching

In the Handbook of Exact String Matching algorithms, it describes the transition set for a basic string matching automaton as: for q in Q (q is a prefix of x) a in $\Sigma$ (q, a, ...
5
votes
1answer
67 views

String searching, where we allow characters to almost-match

Let $\Sigma= \{1,...,n\}$. Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively. I am looking for an algorithm to test whether $Q$ appears as a ...
5
votes
1answer
259 views

From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

I am reading one of Guido van Rossum's essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
1
vote
1answer
78 views

What do you call a function from symbols of alphabet to languages?

Speaking of context-free (and maybe regular? or just any?) languages, what do you call a function defined as follows: Let $\Sigma$ be the alphabet of $L$, $\forall \sigma \in \Sigma: f(\sigma) = L'$, ...
6
votes
1answer
216 views

Finding a certain prefix of a string

Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a ...
1
vote
2answers
59 views

Proving that the reversal of a language reversal is that language

I am trying to prove that with language L, (L^R) ^R =L So that the reversal of the reversal of the language is the original language L. I have proved that before with a string not language (let's ...
1
vote
1answer
50 views

Search a preprocessed text with online queries

We're given a fixed text, and we are presented with a series of online queries of patterns. For each query, the goal is to answer if the pattern exists in the text. Each pattern is a string, and we ...
6
votes
0answers
66 views

What is longest string with no equidistant pairs of equal characters for a given alphabet?

Given a finite alphabet $A$ with $|A|=n$, what is the largest $l$ so that a string $s=a_1...a_l$ of length $l$ exists with $a_i\in A$ so that there is no $i,j,d$ with $i\neq j, d > 0$ so that $a_i ...
6
votes
0answers
208 views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
2
votes
1answer
31 views

Variation to edit distance depending on position still a metric?

The edit distance between two strings $d(w_1, w_2)$ sums up the cost of edit operations that transform one string into the other. If done right, the edit distance is a metric. In particular, the ...
0
votes
0answers
69 views

How to implement auxiliary procedures for LCS algorithm by Hunt/Szymanski

I have read a paper [1] which explains an algorithm for finding the longest common subsequences. I have problem with coding of creating matchlist of Algorithm 2 on ...
1
vote
0answers
22 views

What is an easy-to-implement linear or non-quadratic suffix array construction algorithm?

The algorithm described here in "Linear Work Suffix Array Construction" (2006) has compact C++ code that is too abstract for me to follow. Is that still the current easy-to-implement linear algorithm? ...
2
votes
2answers
86 views

String matching for wildcard-based records

Let's say that we have a string "1.2.3" and want to find a match for it in the following records: 1.2.9 1.4.5 1.*.3 For each ...
2
votes
0answers
78 views

Matching strings in one set to strings in another based on Levenshtein distance

Suppose I have two sets, A and B, which each have one or more strings. I'm looking for an algorithm that'll go through each ...
8
votes
0answers
75 views

What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content?

I have two large files containing paragraphs of English text: The first text is about 200 pages long and has about 10 paragraphs per page (each paragraph is 5 sentences long). The second text ...
5
votes
1answer
76 views

How to speed up process of finding duplicates/similar items in a large amount of strings?

Our software receives documents (in the order of tens of thousands) from various providers, each document flows through a number of steps, one of those steps finds duplicates and similar documents ...
4
votes
2answers
123 views

Are Strings Scalar?

I have always considered strings scalar and the main reason for that is that in programming we treat string values a lot like primitive values. But this and this Wikipedia definitions, as far as I ...
2
votes
0answers
64 views

palindromic factorization

Is there a linear time algorithm that, given a string of length n, tells if it is a sequence of non overlapping palindromes (each of even length, in a binary alphabet)?? I found algorithms that return ...
1
vote
0answers
22 views

How to find close match of levenshtein distance [duplicate]

Let's say we have some function, float distance(String a, String b) { /*...*/ } to find the Levenshtein distance between two strings, and we have a large array ...
7
votes
2answers
484 views

Compression type that can be searched

Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?
8
votes
0answers
89 views

Edit distance of list with unique elements

Levenshtein-Distance edit distance between lists is a well studied problem. But I can't find much on possible improvements if it is known that no element does occurs more than once in each list. ...
6
votes
1answer
63 views

Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes?

I have been reading about the Rabin Karp algorithm and I kept wondering what's the big deal with keeping our rolling hashes values bounded by a value Q? I'd thought that as our integer number ...
0
votes
0answers
20 views

Are there any algorithms or researches on finding local alignments in partially ordered sequences?

The question is a bit unclear, so let me explain. Finding local alignments in sequences like protein sequence is a well studied area in bioinformatics, and I do not think there is any lack of ...
5
votes
2answers
150 views

Universal binary rewriting system

What is the simplest example of a rewriting system from binary strings to binary strings $$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$ that can perform universal computation? Binary string ...
3
votes
0answers
126 views

KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size. But, All the ...
0
votes
2answers
88 views

Minimal length of a string that contains two strings

We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal. Is there an efficient algorithm for this ...
2
votes
0answers
49 views

Can smart recursive search find all optimal solutions for Closest String?

Consider the Closest String problem: Input: Strings $s_1, \dots, s_m \in \Sigma^n$ and $k \in \mathbb{N}$. Question: Is there $s \in \Sigma^n$ for which $d_H(s, s_i) \leq k$ for all $i ...
1
vote
0answers
34 views

Find maximum scoring characters with non overlapping occurrences from a string

I have a problem related to Episode Mining in which I need to find the maximal utility of a episode given its occurrences in an event sequence.But I am presenting the question in a different form so ...
3
votes
0answers
41 views

What is the intuition behind the “edit sensitive parsing” tree?

If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree ...