The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
0answers
26 views

Extracting all substrings using a suffix tree [on hold]

Is there an algorithmically justified way of extracting all substrings of a given string using suffix tree? What I can think of to start from is to build the suffix tree, then start from the root and ...
3
votes
1answer
186 views

Can two strings be matched as disjoint subsequences of a string?

Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a ...
-1
votes
1answer
172 views

Is the running time of Boyer-Moore linear?

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)? Are there any sublinear ...
0
votes
0answers
75 views

Algorithm to merge two incomplete sequences 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): ...
3
votes
2answers
139 views

Most frequent $aXa$ substring

Let $s\in\Sigma^*$ be a string, for some alphabet $\Sigma$. We want to find the most frequent repeated substring $q$ of $s$ such that its first character equals its last one, i.e. the most frequent ...
25
votes
1answer
502 views

Rabin–Karp vs Karp–Rabin

The wise other editors at Wikipedia have declined my request to move the Wikipedia article on the Rabin–Karp algorithm to what I think it should be called, the Karp–Rabin algorithm, on the basis that ...
1
vote
1answer
93 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...
0
votes
1answer
39 views

Unique Identifier Creation and Invalidation

A colleague of mine recently interviewed for a software engineering job, and he was given a problem regarding unique identifier creation and testing for validation. So, the problem is: if a generated ...
2
votes
3answers
264 views

Complexity of ambiguous parsing?

Consider the following problem. We are given a set of words $W \subseteq \Sigma^*$ and a set of sentences $S \subseteq W^*$. The "ambiguous parsing" problem consists, given a word $w \in \Sigma^*$, to ...
0
votes
0answers
109 views

algorithms using string matching

Do there exist algorithms in computer science in which one of the sub protocol involves string matching (which can be done in linear time)? Forgetting the practical motivations, i am curious if string ...
7
votes
0answers
125 views

Simplifying the disjoint union of wildcard strings

Setting: patterns with "don't care" symbols, binary alphabet. For example, pattern $x = 001?$ represents the set $L(x) = \{0010, 0011\}$. We are given a set $P$ of disjoint patterns: $L(x) \cap L(y) ...
12
votes
2answers
350 views

Edit distance with move operations

Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the ...
10
votes
4answers
3k views

Can Suffix trees be used to find all common substrings?

I am trying to use suffix trees to compare string sequences. I have found implementations/theory for the longest common sub string problem using suffix trees. However, What i am looking for is a ...
0
votes
0answers
422 views

suffix tree: about Ukkonen's algorithm

I have specific question about suffix trees. I am reading the book Algorithms on strings_trees and sequence. I cannot understand details of Ukkonen's algorithm for constructing suffix trees. Why ...
1
vote
2answers
259 views

Matching substrings within two strings

I'm currently thinking about the following problem: Given two strings $S,T$ over an alphabet $\Sigma$, return back a list $L$ of common substrings described by their length and positions within them. ...
18
votes
2answers
498 views

n-dimensional pattern matching

What are some known results for finding an exact n-dimensional subarray inside a n-dimensional array? In 1D, it is just a string matching problem, KMP does it in linear time. In 2D, this paper shown ...
0
votes
1answer
694 views

Algorithm: Find the first k longest substrings between two similar strings

Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.
-4
votes
3answers
119 views

Text Analyze and Processing

What algorithms do you know regarding text analyze/processing? Detailed, I need to "find out" the most used words, sentences, words' combinations, their category etc (these are just examples, moreover ...
9
votes
3answers
414 views

Permutation pattern matching in strings

Loosely speaking, permutation pattern matching deals with problems of the following kind: Given permutations $\pi$ in $S_n$ and $\sigma$ in $S_m$, with $m\leq n$, does $\pi$ contain a subsequence ...
6
votes
1answer
236 views

Fast algorithm for scoring a sequence

Let us define: $U = \left\{ u_j \right\}, 1 \leq j \leq N = 2^{L}$, the set of all different binary sequences of length $L$. $V = \left\{ v_i \right\}, 1 \leq i \leq M = \binom{L}{k}2^{k}$, the set ...
8
votes
1answer
393 views

Deciding if a wildcard string is completely matched by another wildcard string in a set

Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the ...
4
votes
1answer
234 views

How to calculate this string-dissimilarity function efficiently?

Migrated from stackoverflow. Hello, I was looking for a string metric that have the property that moving around large blocks in a string won't affect the distance so much. So "helloworld" is ...
16
votes
6answers
2k views

Computing the Levenshtein distance quickly

Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance. The naive approach is, ...
2
votes
1answer
295 views

Using compression to improve edit distance computation

I am doing a seminar on a paper titled "Unified Compression-Based Acceleration of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common ...
-1
votes
1answer
278 views

Locate “N Gram” substrings that are smallest distance away from a target string N character long

I am looking for an algorithm, or code, preferably in Python that would help me locate substrings, N characters long, of exisiting strings that are closest to a target string N character long. ...
8
votes
4answers
648 views

Intermediate/Coding representation for Levenshtein Distance

The phrases: The quick brown fox jumps over the lazy dog [A] and The uick brown fox jumps oower the lazy dog [B] can be compared using Levenshtein Distance algorithm to determine ...