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

learn more… | top users | synonyms

1
vote
0answers
80 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
52 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 ...
1
vote
2answers
60 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
49 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 ...
1
vote
1answer
56 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
83 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
38 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
151 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
40 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
86 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
104 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 ...
5
votes
3answers
200 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
37 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
71 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
22 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
36 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
56 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
43 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
21 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
58 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
102 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
82 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
104 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
36 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
68 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
85 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
54 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
61 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
201 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
114 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
65 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
32 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 ...
3
votes
1answer
106 views

String matching for all suffixes

Given a string $(a_0,a_1,\ldots a_n)$. I want to find the length of the longest common prefix of the substrings $(a_0,a_1,\ldots a_{n-1})$ and $(a_1,a_2,\ldots a_n)$. I know this has atleast $O(n)$ ...
3
votes
1answer
86 views

exact matching between two strings - linear edit distance?

This is the problem, given a string with characters from: a-z, ., *, and another string with ...
0
votes
1answer
1k views

Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity

Problem Statement: Suppose we a thousands of words and we need to maintain these words in a data structure in such a way that we should be able to find all anagrams for a given string. I tried to ...
2
votes
2answers
343 views

Confusion about finite automata construction in Knuth–Morris–Pratt algorithm

There is one point I don't understand in the DFA construction for mismatch cases. Here is the lecture note I watched, which describes how to handle mismatched characters during the DFA construction ...
3
votes
2answers
44 views

Drawbacks of repeating a single pattern matching procedure for many patterns

One naive approach in solving multiple pattern matching problem is to call single pattern matching procedure on each of the pattern. There must be some drawbacks in this approach, given the variety ...
3
votes
0answers
293 views

A comparison between Aho-Corasick algorithm and Rabin-Karp algorithm

I am working on multiple patterns search matching algorithms and I found that two algorithms are the strongest candidates, namely Aho-Corasick and Rabin-Karp in terms of running time. However, there ...
2
votes
1answer
60 views

A framework to capture common variation of sequence alignments

The global alignment problem can be generalized by setting the cost of some boundary gaps to 0. Gaps at both end in both strings have 0 cost, then we get the semiglobal alignment. Gaps are at the ...
1
vote
1answer
1k views

Number of distinct substrings in a string

From what I have come to understand, the best way to implement it is to use the suffix array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$. The answer can be obtained by $$ ...
3
votes
2answers
312 views

Automaton for substring matching

Given s as a string of some alphabet, what is the best known algorithm to compute a corresponding automaton that accepts any string that contains s? I am mostly intrested of the lowest time ...
6
votes
1answer
149 views

Semi-local Levenshtein distance

If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all ...
2
votes
1answer
182 views

Find longest common subsequence in limited space

Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS). Example: A longest common subsequence of ...
2
votes
1answer
314 views

Shortest sub-sequence of one string, that's not a sub-sequence of another string

Given two strings $x$ and $y$ over the alphabet $\{A,C,G,T\}$, I'm trying to determine a shortest string $z$ such that $z$ is a subsequence of $x$ and not a subsequence of $y$. Example: a shortest ...
4
votes
3answers
129 views

How to find specificity of a regex match?

I'm thinking about a routing system. Imagine I have the two following regexes pathpart1/pathpart2 => specific match that routes to controller1 .* => catch-all that routes to controller2 And I let ...
1
vote
1answer
195 views

Unable to understand control flow in KMP algorithm

I am facing problem in understanding the KMP algorithm as given in the book "Introduction to Algorithm" by Cormen et. al. (Chapter 32): With respect to the above algorithm, I have following ...
3
votes
0answers
142 views

Distinguishing probabilistic, deterministic, and fuzzy matching methods

I have two datasets that I am trying to match to one another. One dataset's contents is a subset of the other, but contains typographical errors of varying types and magnitude. I am applying the ...
1
vote
2answers
612 views

How do we find the optimal modulus q in Rabin-Karp algorithm?

I asked a similar question here on Rabin Karp algorithm. My present question is, how do we find the best $q$ (i.e modulus)? What is the criterion? We need to choose a $q$ which will be quick to ...