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

learn more… | top users | synonyms

1
vote
0answers
21 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
9 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 ...
1
vote
0answers
29 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
48 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
66 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. ...
0
votes
1answer
42 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
20 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
24 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 ...
2
votes
0answers
24 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
116 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
63 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
68 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
87 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
39 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
36 views

What is MongeElkan distance between words?

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
0
votes
1answer
70 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
30 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
46 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
43 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
113 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
209 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
0answers
53 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
291 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
157 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
169 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
188 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
78 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
44 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
88 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
57 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
176 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
585 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
74 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, ...
2
votes
1answer
135 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
125 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 ...
-1
votes
1answer
525 views

Suffix automaton algorithm to find occurrences of substrings

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
219 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 ...
3
votes
3answers
94 views

Correct term for “string consisting of words”

In a paper I am writing I want to make distinction between (1) string consisting of any characters and (2) string consisting of a chain of words from known language, with possible delimiters. My ...
7
votes
0answers
334 views

Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
6
votes
3answers
1k views

Word Frequency with Ordering in O(n) Complexity

During an interview for a Java developer position, I was asked the following: Write a function that takes two params: a String representing a text document and an integer providing the ...
0
votes
1answer
46 views

Conditional LCS problem

A producer wants to arrange couples of boys and girls for a dance. There are n boys arranged in a row [A1...An] in some certain order and n girls arranged in a different row [B1...Bn], also in some ...
3
votes
1answer
308 views

Find longest common substring using a rolling hash

The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring ...
0
votes
1answer
39 views

Why is fail[1] in KMP Algorithm always 0?

I'm studying KMP Algorithm. In the failure function (or the sp table), why do we always assign the value 0 to the first element (character) of the pattern? I understand about the later elements of the ...
0
votes
1answer
94 views

KMP Algorithm Example

I'm studying KMP algorithm and I'm stuck on an example. Suppose my text is "I am queen." and my pattern is "q". The sp table will have only one value, q and it's sp index will be 0. Mismatch will ...
3
votes
2answers
61 views

How do learn the most important nodes in a tree?

I have a list of 20000 words and how often they appeared in a set of 500 newspaper articles. I am trying to build a stemmer which chops off suffuxes from each words, so ...
1
vote
1answer
58 views

Can a Markov Algorithm Replace the Empty String?

Suppose I have a Markov Algorithm, and I have some rules, such that after execution of these rules, the remaining string is either "a", "b", or the empty string, "". Then I have three terminal rules ...
1
vote
1answer
29 views

Inserting a sentence into search trees

Let's say you have the following sentence: "This is my first cs question posted here". How would I go about inserting the sentence into a search tree. Do I assign each word a number value and perform ...
1
vote
1answer
105 views

Turing machine with repeated strings

How would I go about making a Turing machine to accept the following language L? $$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$ I was thinking counting the number of symbols in the input ...