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

learn more… | top users | synonyms

3
votes
0answers
18 views

Fast generalised suffix array construction: lower than O(n^2 log n)

There is a lot in the literature about linear time constructions for suffix arrays; DC3, radixSA46, and more... However, these, I believe, are only for suffix arrays; with a single string input. Are ...
0
votes
1answer
87 views

Algorithm for length of longest common subsequence

The case of multiple strings. A slight modification of the dynamic programming algorithm for two strings is used as a subroutine. Here is the pseudo code: ...
0
votes
1answer
23 views

How to model “name similarity”?

I am new to machine learning. But have basic understanding of the concepts. Problem statement : We humans won't perceive much difference between "Tim Cook" and "Tim C0ok". ( 0 is been replaced with ...
2
votes
1answer
67 views

What kinds of problems are modeled by a recursive definition of a set of strings?

Given this definition: The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by: BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string) RECURSIVE ...
2
votes
1answer
45 views

Why isn't a binary counter used for generating $k$-combinations?

I have been looking at algorithms that allow you to generate $k$-combinations of a given string. My question is that why isn't the algorithm used to generate power sets used to generate the ...
2
votes
3answers
53 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
137 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
30 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
27 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
20 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
58 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 of $...
3
votes
0answers
55 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
47 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
91 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
116 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
38 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
32 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
186 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
103 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
52 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
82 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 idea ...
3
votes
1answer
126 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
51 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
25 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, qa)...
5
votes
1answer
68 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
265 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
81 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
220 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
60 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
278 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
35 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
104 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
90 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
79 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
78 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
135 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
68 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
488 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
97 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
66 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 ...
6
votes
2answers
161 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 ...