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

learn more… | top users | synonyms

0
votes
1answer
16 views

What is MongeElkan distance between words?

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
0
votes
1answer
39 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
23 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 ...
0
votes
0answers
38 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
35 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
90 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
180 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

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
103 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
64 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
67 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 ...
1
vote
0answers
16 views

examples of strings that is not in the set [closed]

I'm kind of struggling with finding a string that is not in this set {w: for some u ∈ Σ*, www = uu} where Σ = {a,b} from what I understand, the set of Σ* is, {E, a, b,aa, ab, ba, bb, aaa, ...} if w ...
5
votes
1answer
105 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
70 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
43 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
86 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
54 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
140 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
230 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
52 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
67 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
112 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
87 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 ...
-2
votes
1answer
353 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
101 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
90 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 ...
5
votes
0answers
220 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
751 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
45 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 ...
2
votes
1answer
215 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
26 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
70 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
59 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
49 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
24 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
79 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 ...
1
vote
2answers
115 views

Searching for a string of numbers in a large digit sequence [closed]

How would one search for a string of digits in a large digit sequence? For example, I'd like to search for 351814 in Euler's number. I'm not too keen on computer ...
2
votes
2answers
84 views

What are these special strings called?

Is there any specific name for strings of data that have well defined format ? For example URLS, domain names, IP Addresses, Email addresses, File Paths etc. are all having well defined delimiters and ...
1
vote
3answers
110 views

Is there a basic proof that there exists some edit distance between two strings?

Title says it all pretty much. I do realize that often edit distance is defined as the minimum number of operations needed to transform one string to another, but I want something to point to that's ...
2
votes
0answers
38 views

What is hiding behind amortized constant delay enumeration?

The following may contain errors. It is precisely because I am not sure I understand the topic that I am asking questions. I do not have books about it and could not find an adequate reference on the ...
1
vote
1answer
69 views

Are algorithms for searching text vs searching numbers fundamentally different?

I face this problem a lot while searching phone numbers and bank account numbers, when I do remember it partially. I save a draft in gmail with the content ...
4
votes
3answers
94 views

Efficiently representing a set of sets

(The question is an extension of this unanswered question on stackoverflow) If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in ...
0
votes
1answer
71 views

string matching vs integer matching

How different are string matching and integer matching in terms of time complexity? I'm asking this especially in relation to Rabin Karp algorithm. Why is it faster to compute hash code for every ...
0
votes
0answers
100 views

O(pattern_length) failure function in kmp algorithm

consider the pseudo code for calculating failure function: I partial understand the algorithm. KNUTH-MORRIS-PRATT FAILURE (P) Input: Pattern with m characters Output: Failure function f for P[i . ...
3
votes
3answers
268 views

Algorithm Request: “Shortest non-existing substring over given alphabet”

I'm looking for an (efficient) algorithm to solve the following problem: Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
2
votes
0answers
66 views

Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
1
vote
1answer
116 views

Fast ways to compute the smallest prime with a given substring?

So, I've got this problem: Given a string $\omega\in\{0,\ldots,9\}^*$, find the smallest prime number (in base 10) that contains that string, or otherwise returns 0. What I'm asking is a fast ...
1
vote
1answer
26 views

Trying to tag parts of a word and keep track of any changes that happen to those parts

I'm a researcher working with a language that has gone through phonological changes through time. I would like to tag parts of a word (i.e. prefix, stem, suffix) and then apply those phonological ...
-1
votes
1answer
66 views

Check if there exist A and B such that S=A+B and T=B+A

Two strings $S$ and $T$ are said to be conjugate if there are two non-empty strings $A$ and $B$ such that $S = A+B$ and $T = B+A$ ($+$ is concatenation). How can I find if two strings are conjugate or ...
1
vote
1answer
40 views

How can a Turing machine run another machine for an infinite amount of strings?

The proof in my textbook, that $E_{TM}$ can be decided by oracle machine $O^{A_{TM}}$, uses a Turing machine $P$ such that for an input $w$: $P$ runs the Turing machine $M$ on all strings of ...