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

learn more… | top users | synonyms

2
votes
0answers
48 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
62 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 ...
0
votes
0answers
27 views

Algorithm for special variation of sequence alignning needed [closed]

Its pretty hard to strictly define what im trying to achieve here (any help would be appriciated), but is there an algorithm that does a combination of local sequence alignment with immunity to ...
2
votes
0answers
23 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
21 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 ...
1
vote
0answers
25 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 ...
5
votes
1answer
43 views

Hamiltonian circuit for a family of graphs

For $\Sigma = \{a,b\}$, let $S_n = \{w\mid w \in \Sigma^{*} \land |w| = n\}$. Let $C_n \subset \Sigma^{*}$ be the language of circular strings that contain as substrings all elements of $S_n$. For ...
3
votes
1answer
120 views

Algorithm to search substring in a circular string?

I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt. However, as far as I ...
2
votes
1answer
43 views

Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases: ...
2
votes
2answers
436 views

What are the k characters which make the most complete words?

Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ ...
1
vote
1answer
37 views

Sequence alignment with one to many characters

I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with ...
0
votes
0answers
13 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
2
votes
0answers
59 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
1
vote
0answers
81 views

How can I learn Sunday's string searching algorithm?

How does Sunday's string searching algorithm work? I am highly unskilled in processing mathematical lingo, so I would appreciate a use case/example. A link would be ok. I tried searching the first 6 ...
2
votes
3answers
40 views

Existence of functions that only tests memberships without revealing any information about the members

Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically ...
2
votes
1answer
74 views

Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one. ...
-1
votes
2answers
62 views

Finding A String Using A Suffix Array/Table

Is it possible to find out a string only having its corresponding suffix array/table and knowing that the string contains only, for instance, letters "f", "g", "r"? If so, how is that possible?
-1
votes
1answer
25 views

String distance metric for possibly truncated words

I am looking for the optimal string distance metric to indicate similarity/difference between possibly truncated words. For example, I would like to find the distance metric between the name "Richard" ...
1
vote
0answers
27 views

Constructing a TM from empty string

Hey I want to construct a deterministic Turing Machine, which out of an empty string tapes six consecutive 1s when halt. I have a question, is it possible to create such without transitions from final ...
3
votes
0answers
27 views

Need help understanding this heuristic used for approximate string searching through an FSA

The paper I'm looking at: http://dingo.sbs.arizona.edu/~mhulden/hulden_sepln_2009.pdf Explanation of the algorithm (from my understanding anyway): A word is inputted into the automaton and from each ...
1
vote
3answers
121 views

Fastest possible way to check what of X is in a string

I am trying to speed up one of my application, one of the places where I can speed up is in my test if a string contains an array of strings. example: I have the matches "dog", "cat" "apple" and the ...
0
votes
1answer
78 views

Efficiently count frequency of n-grams at start of words

I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as: aaaaa aaaab aaaac aaaad ..... and I have a txt file (organized in rows) with all English words. I have to find ...
2
votes
1answer
84 views

How to create a suffix tree by hand

I will soon have to be able to draw a suffix tree of a word on an exam. I tried to understand the different algorithms available, but they seem rather complicated to do "by hand". I do not see a ...
5
votes
1answer
99 views

How do I efficiently checking if a string matches any substring in a collection

I have a collection of substrings "this" "is" "a" "antelope" I need to look at any given string and answer the question "Are any of the given substrings in this ...
4
votes
0answers
59 views

Number of distinct substrings

I know how to find the number of distinct substrings for a string (using suffix arrays) and I was wondering if there was a way to find this number for all of its prefixes. I already have an $O(N^2)$ ...
0
votes
1answer
56 views

What is MongeElkan distance between words?

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
0
votes
1answer
88 views

FM-index - print all patterns

How is it possible to print all patterns, of length k, contained in a string using FM-index and burrows-wheeler transform? PROBLEM DETAIL: I think it's better to leave more details regarding my ...
1
vote
0answers
33 views

Modify Damerau–Levenshtein distance to allow reversals of longer substrings

Is there a way to modify the Damerau–Levenshtein distance algorithm to allow the transposition of substrings? By this I mean that instead of simply turning "ba" to "ab" you could calculate "worra" to ...
1
vote
0answers
51 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
4
votes
0answers
45 views

Polynomial time algorithms on strings [closed]

I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known. To be more precise, let $\Sigma$ be a finite alphabet. I am looking ...
2
votes
3answers
119 views

Computing the closest match of an automaton and a string

I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting ...
7
votes
1answer
240 views

Given n strings, is one of them a substring of another?

Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$. I would like to know whether any of those strings is a substring of any other string in the collection. In other words, I'd like an ...
1
vote
1answer
35 views

FM-index and pattern search with wildcards

in one of my algorithm courses i'm studying the FM-Index. In one of the exercise I'm trying to do I was asked to give a procedure to search patterns of the form w* ...
1
vote
0answers
65 views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm or a single class Java/C implementation? I have access to original two papers, but they do not show the ...
2
votes
1answer
382 views

compressing a set of binary strings with fixed length

I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all ...
0
votes
1answer
206 views

Which algorithm to use to find all common substring (LCS case) with really big strings

I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need to find the LCS and other ...
2
votes
2answers
217 views

Segmenting an English string with no spaces using dynamic programming

Suppose you have a function quality(x) that returns the quality of a sequence of letters x. Given a string such as ...
5
votes
1answer
238 views

Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ ...
1
vote
2answers
89 views

Enumerate All Possible Strings Over Alphabet

I am given the following decision problem: A program $ \Pi $ takes as input a pair of strings and outputs either $true$ or $false$. It is guaranteed that $\Pi$ terminates on any input. Does there ...
1
vote
1answer
46 views

Algorithm to merge two incomplete lists of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
1
vote
0answers
91 views

Boyer-Moore with Don't Cares

I have been doing a lot of research into pattern matching algorithms. For some background I am searching a long binary alphabet text consisting of considerably more 0s than 1s. The individual ...
1
vote
2answers
59 views

Is string matching and replacement considered in formal languages?

Is string matching and replacement, as an operation on strings or on formal languages, considered in formal languages? For example, the family of regular languages, or the family of context free ...
4
votes
0answers
184 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: $$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) ...
1
vote
2answers
836 views

Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
0
votes
1answer
54 views

What string operations are basic

What string operations are basic in the sense that the other string operations can be represented in terms of them? Here is a list of string operations off the top of my head (not necessarily a ...
2
votes
1answer
78 views

Efficient algorithm for iterated find/replace

I'm looking for an algorithm for doing iterated find/replace, where the act of finding the replacement list of tokens for a given find is slow. Specifically: I have a function, ...
3
votes
1answer
153 views

Can not understand idea of the KMP algorithm

I am using Sedgewick's Algorithms (4th ed) to learn Knuth-Morris-Pratt substring search algorithm. The key step is construct the DFA array corresponding to a given pattern. The authors say: The ...
1
vote
1answer
169 views

Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation

Given a string S of length n characters, is it possible to calculate the Hash of its substring [i, j] (From index i to index j. Inclusive) in O(1) using some form of precomputation ? Maybe a ...
-3
votes
1answer
660 views

Suffix automaton algorithm to find occurrences of substrings [closed]

Here is an attached link to a problem, the Substring query problem that I am trying to solve. It requires the use of suffix automaton,but I could not understand what is a suffix automaton. Can ...
2
votes
1answer
252 views

Why is the base used to compute hashes in Rabin–Karp always primes?

The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$ h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i, $$ where $b$ is prime (all computations ...