Questions about sequences of symbols, sets thereof and their properties as well as uses.
1
vote
1answer
54 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
78 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 ...
3
votes
3answers
60 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
67 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
57 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
115 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
66 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
1answer
85 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 ...
10
votes
0answers
125 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
308 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:
...
3
votes
2answers
142 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
86 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
91 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
34 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
124 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
40 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
144 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 ...
2
votes
1answer
172 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
66 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
68 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
272 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
176 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
277 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 ...
4
votes
2answers
327 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 ...
1
vote
1answer
157 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 ...
4
votes
1answer
91 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 ...
4
votes
2answers
283 views
Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.
That is, for each suffix of $r$ ...
3
votes
2answers
419 views
Finding the number of distinct permutations of length N with n different symbols
I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are.
For example if the string is of length ten as $w = aabbbaabba$, the total number ...
6
votes
3answers
1k views
Fastest algorithm for finding the longest palindrome subsequence
First of all we must read a word, and a desired size.
Then we need to find the longest palindrome created by characters in this word used in order.
For example for size = 7 and word = "abcababac" the ...
17
votes
4answers
557 views
Finding interesting anagrams
Say that $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ are two strings of the same length. An anagramming of two strings is a bijective mapping $p:[1\ldots n]\to[1\ldots n]$ such that $a_i = b_{p(i)}$ ...
11
votes
2answers
490 views
Efficient map data structure supporting approximate lookup
I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited ...
5
votes
3answers
400 views
Counting different words in text using hashing
I am still fighting with hashing and I am ask myself: what is the most efficient way to count the number of different words in a text using a hash table?
My intuition says that applying the hashcode ...
3
votes
2answers
215 views
Turn one string into another with single letter substitions
I want to turn one string into another with only single letter substitions. What is a good way to do this, passing through only valid words in between (this website has some examples)?
Valid here ...
7
votes
2answers
205 views
How many strings are close to a given set of strings?
This question has been prompted by Efficient data structures for building a fast spell checker.
Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, ...
3
votes
1answer
107 views
Randomized String Searching
I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m < n$.
I want to state an algorithm that runs in time $O(n)$ where we assume that ...
6
votes
1answer
650 views
Connection between KMP prefix function and string matching automaton
Let $A_P = (Q,\Sigma,\delta,0,\{m\})$ the string matching automaton for pattern $P \in \Sigma^m$, that is
$Q = \{0,1,\dots,m\}$
$\delta(q,a) = \sigma_P(P_{0,q}\cdot a)$ for all $q\in Q$ and $a\in ...
19
votes
3answers
883 views
Efficient data structures for building a fast spell checker
I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to ...
4
votes
6answers
741 views
C++ Strings vs. Character Arrays
Why do you think it is that most C++ instructors teaching college level computer sciences discourage or even forbid using strings for text, instead requiring students to use character arrays?
I am ...
6
votes
1answer
157 views
What is a formula for the number of strings with no repeats?
I want to count the number of strings $s$ over a finite alphabet $A$, that contain no repeats, and by that I mean for any substring $t$ of $s$, $1< |t| < |s|$, there is no disjoint copy of $t$ ...
8
votes
2answers
1k views
dynamic programming exercise on cutting strings
I have been working on the following problem from this book.
A certain string-processing language offers a primitive operation which splits a string into two
pieces. Since this operation ...
14
votes
1answer
326 views
Does every large enough string have repeats?
Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for ...
15
votes
0answers
441 views
Is there a 'string stack' data structure that supports these string operations?
I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing ...
7
votes
1answer
190 views
Compression of domain names
I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
