Hot answers tagged

25 votes

How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

Yes, the entire dictionary is compared against each word. This can be fast by using a trie and an algorithm similar to Levenshtein's. I have built my own spelling corrector that checks words against a ...
user avatar
19 votes

How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

Companies with search engines (e.g. Microsoft or Google) don't always directly search for the string with the smallest Levenshtein distance. They have a huge database of search queries, from which ...
user avatar
  • 18.9k
18 votes
Accepted

Why is the base used to compute hashes in Rabin–Karp always primes?

A quick recap first. We are looking for a pattern $P[1\ldots m]$ in a string $S[1\ldots n]$. The Rabin-Karp algorithm does this by defining a hash function $h$. We compute $h(P)$ (that is, the hash of ...
user avatar
  • 18.9k
14 votes
Accepted

Longest common substring in linear time

Let $m$ and $n$ be the lengths of two given strings, Linear time assuming the size of the alphabet is constant. Yes, the longest common substring of two given strings can be found in $O(m+n)$ time, ...
user avatar
  • 34.1k
13 votes

Word Frequency with Ordering in O(n) Complexity

I suggest a variation of distribution counting: Read the text and insert all the word encountered into a trie, maintaining in each node a count, how often the word represented by this node has ...
user avatar
  • 6,519
12 votes
Accepted

Compression type that can be searched

Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space. These are essentially compressed suffix arrays or suffix trees, which have a lot of ...
user avatar
  • 1,254
12 votes

How to check if two strings are permutations of each other using O(1) additional space?

Denote the arrays by $A,B$, and suppose they are of length $n$. Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space: Compute the minimum values of ...
user avatar
11 votes
Accepted

Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes?

Yes, in practice you can get by fine with just letting the computations overflow. You are effectively working modulo $2^{32}$. It also has the advantage of not requiring an (expensive) modulo ...
user avatar
11 votes
Accepted

Assigning a unique representation to equivalent circular queues

Enumerate all possible rotations of the queue. Take the lexicographically first of them. Use this as your representative. If you want a short index into a hash table, take the hash of that. Then ...
user avatar
  • 141k
9 votes
Accepted

Algorithm to search substring in a circular string?

Create a temporary source string by concatenating itself together until the length of the source string is at least twice the length of the search string. The source string must be concatenated at ...
user avatar
9 votes
Accepted

From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list: Read the list in chunks of $k$, convert them ...
user avatar
8 votes
Accepted

Find all substrings that fit the mask with asterisks

Yes, there is a more efficient algorithm. Your algorithm can take exponential time. You can check whether there exists any match in $O(nm)$ time, where $n$ is the length of text and $m$ is the ...
user avatar
  • 141k
8 votes

How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

I just tried and found that the spelling checker on my phone finds a perfectly fine replacement for “gekki wirkd”. Look at your keyboard, and it is obvious. A good spelling checker does much better ...
user avatar
  • 25.2k
8 votes
Accepted

What is the name of the following binary encoding?

Your encoding is not self-terminating, which makes it somewhat less useful than encodings such as universal codes. Given an integer $n \geq 0$, write $n+2$ in binary without leading zeroes, and remove ...
user avatar
7 votes

Have I invented a new data structure?

I've never seen this data structure before. However, it doesn't seem like a good choice for storing a set of words, for most purposes. I see three significant disadvantages: Performance. Looking up ...
user avatar
  • 141k
7 votes
Accepted

How to check if two strings are permutations of each other using O(1) additional space?

The naive approach would be building histograms of both strings and checking whether they are the same. Since we are not allowed to store such a data structure (whose size would be linear to the size ...
user avatar
  • 599
7 votes

Find all n bit numbers with k ones and unique under circular shift

Binary strings considered up to rotation are known as necklaces. You are interested in enumerating binary necklaces with given density. You can find one solution in Wang and Savage, A Gray Code for ...
user avatar
6 votes

Comparison between Aho-Corasick algorithm and Rabin-Karp algorithm

Asymptotic running time analysis is not likely to be the best tool to pick between these two algorithms: asymptotic analysis ignores constant factors, and the constant factors will be critical here. ...
user avatar
  • 141k
6 votes

What string operations are basic

There are many "complete bases" for operations on strings. One is based on the representation $$ \Sigma^* = \epsilon + \Sigma \Sigma^*. $$ In words, a string is either empty or is composed of a ...
user avatar
6 votes

Given n strings, is one of them a substring of another?

You can build a suffix tree in linear time and check if there's an inner node that corresponds to a full string (constant time per node). In more detail, assume we are given strings $s_1, \dots, s_n \...
user avatar
  • 70.9k
6 votes
Accepted

How do I efficiently checking if a string matches any substring in a collection

I think the Aho-Corasick algorithm is your best bet here. The algorithm is designed to solve the set matching problem (essentially the one you've defined), in which you want to determine which ...
user avatar
6 votes

Universal binary rewriting system

Rule 110 is a binary rewriting system that can perform universal computation, i.e., it has been proven to be universal. It can be implemented by a finite-state transducer: it needs only finite state. ...
user avatar
  • 141k
6 votes

How to speed up process of finding duplicates/similar items in a large amount of strings?

Edit distance is definitely not the way to proceed. The standard approach toward near-identical document deduplication is to compute hashes of shingles. Here's one way to do it: Compute a set of k-...
user avatar
6 votes

Is there a data structure for efficiently searching a string that contains a given substring?

You could append all of the $n$ strings together, and add an arbitrary character '\$' not in the pattern to separate them. Then you could apply the Z algorithm on your original pattern and this new ...
user avatar
  • 280
6 votes
Accepted

Finding the smallest string that contains a given set of substrings

This problem is called shortest superstring problem. John Gallant, David Maier and James Astorer proved it is NP-hard in 19791. Given two strings $A$ and $B$, let $|A|$ denote the length of $A$, and ...
user avatar
  • 7,250
6 votes
Accepted

What is an efficient data structure for prefix matching?

A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time. If you care about constant factors, the only way to know what will be optimal is to try ...
user avatar
  • 141k
5 votes

Is there a 'string stack' data structure that supports these string operations?

I thought for quite some time, but didn't find the problem with doing all of your operations in the most stupid possible way in a trie-like DAG structure: Add-Prefix-Set Create a trie of strings from $...
user avatar
  • 136
5 votes
Accepted

Longest Repeated (Scattered) Subsequence in a String

The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks. Buss and Soltys proved NP-completeness of this problem [1] by reducing 3-Partition ...
user avatar
  • 826
5 votes

Suffix automaton algorithm to find occurrences of substrings

Given a FA $M$ accepting a language $L$, a suffix automaton is one which accepts the language of all suffixes of strings in $L$. In other words for a language $L$ over an alphabet $\Sigma$, $$ \...
user avatar
  • 14.6k
5 votes

Complexity of a naive algorithm for finding the longest Fibonacci substring

Say that $F(n)$ occurs at some position if the substring starting at that position is compatible with either $F(n)$ or its complementation. How close can occurrences of $F(n)$ be? Take as an example $...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible