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

learn more… | top users | synonyms

1
vote
1answer
33 views

Searching for a string of numbers in sequence

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 science, I'm a pure math major, so I ...
2
votes
2answers
79 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
98 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
31 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
52 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
74 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
45 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
37 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
176 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
59 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
107 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
25 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
64 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
29 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
96 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
74 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
603 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
258 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
39 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
231 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
55 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
824 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
249 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
131 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
158 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
235 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
103 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
161 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
118 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 ...
0
votes
1answer
489 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 ...
1
vote
0answers
194 views

Problem with Cormen's treatment of the Rabin-Karp algorithm

I am reading chapter 32 - String Matching from the book "Introduction to Algorithms" 3rd edition Cormen et al. The Rabin-Karp Algorithm is not clear to me despite heaving read it several times. ...
2
votes
2answers
196 views

What is Harrison hashing, its applications in web search engines?

What is Harrison hashing and what are its applications in web searching? Can some one give me some relevant information? Update: I found it here , and is a part of M.Tech syllabus of a friend ...
13
votes
0answers
236 views

How does the runtime of the Ukkonen's algorithm depend on the alphabet size?

I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time. Here is a citation ...
6
votes
3answers
1k views

Is there an algorithm for checking if a string is a catenation of palindromes?

Is there a linear-time algorithm to check that a sequence of characters is a concatenation of palindromes? The only thing that comes to my mind is the naive solution: ...
4
votes
2answers
952 views

Algorithm for building a suffix array in time $O(n \log^2 n)$

I've been working with suffix arrays lately, and I can't find an efficient algorithm for building a suffix array which is easy to understand. I have seen in many sites that there is an $O(n \log^2 ...
5
votes
2answers
111 views

Behavior of iterative application of LZ77

I have been experimenting with LZ77 (naively $O(n^2)$ runtime, infinite window). Applying it to the 7th Fibonacci word $abaababaabaab$ yields the correct LZ factorization: $\qquad ...
2
votes
4answers
164 views

Optimal algorithm for finding all ngrams from a pre-defined set in a text

I'm thinking about the optimal algorithm for the following problem: Input data: a text, say it's an article about 5-50 pages. a set of ngrams (ngram strings, n>2), of arbitrary length, could be ...
2
votes
1answer
36 views

terminology for grouping words in a string?

We commonly create sub-groups of strings in one particular algorithm implementation. I just want to know in CS literature is there any standard name for such kind of grouping. For e.g. ...
1
vote
1answer
385 views

String similarity problem

We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet. We consider the problem of converting $x$ to $y$. Using the following operations: ...
2
votes
0answers
105 views

Myers' Fast bit-vector algorithm in plain English?

Inspired by this question on Suffix Trees, and the fabulous winning answer, I would hereby ask for a similar explanation of Myers' Fast Bit-Vector Algorithm for Approximate String Matching Based on ...
4
votes
2answers
241 views

Fuzzy string matching algorithm with allowed events?

I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions ...
1
vote
1answer
269 views

Why does a suffix tree have a linear number of nodes (relative to input string size)?

Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.
4
votes
1answer
87 views

What are the effects of the alphabet size on construct algorithms for suffix trees?

For what size alphabet does it take longer to construct a suffix tree - for a really small alphabet size (because it has to go deep into the tree) or for a large alphabet size? Or is it dependent on ...
2
votes
1answer
81 views

Rechecking contiguous characters (as in run length encoding)

So I have a fun little problem. It will take a minute to explain, but the situation is conceptually very simple. Suppose you have a string of characters, which is interpreted as groups of one or more ...
5
votes
1answer
1k views

Find the longest repeated pattern in a string

I'm looking for an efficient algorithm to find the longest repeated pattern in a string. For example, consider the following string of numbers: ...
6
votes
1answer
184 views

Represent string as concatenations

If $S_1,S_2$ are set of strings, then $S_1S_2 = \{s_1s_2|s_1\in S_1, s_2\in S_2\}$. $S^0=\{\epsilon\}$, $\epsilon$ is the empty string. $S^n = S^{n-1}S$. Two related problems about represent string ...
2
votes
2answers
565 views

Dynamic programming table for finding similar substrings is too large

Substring Diff Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots ...
7
votes
2answers
1k views

Fast k mismatch string matching algorithm

I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P ...
3
votes
1answer
500 views

Semantic clustering

I have a very specific question about semantic clustering. I have a list of words/phrases. I want to run an intelligent semantic clustering algorithm on this list. Please let me know what the ...
5
votes
1answer
136 views

Find string that minimizes the sum of the edit distances to all other strings in set

I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs. Is there an algorithm for finding the string $x$ which minimizes the sum of the ...