# Tag Info

### 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 ...

### 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 ...
• 22.6k
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, ...
• 39k

### 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 ...
• 278k
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 ...
• 163k
Accepted

### Count number of non-contiguous occurrences in string

A dynamic programming algorithm in $\mathcal{O}(|S| |T|)$ should do the trick. Let's denote $S = s_1…s_m$ and $T = t_1…t_n$. For $0\leqslant i \leqslant m$, $0\leqslant j \leqslant n$, let $N(i, j)$ ...
• 15.9k
Accepted

### Can we prove that any set of finite strings without substrings is finite?

Assuming that by substring you mean consecutive substring, take $$L= \{10^n1 : n \ge 0\}.$$ On the other hand, if you refer to nonconsecutive substrings, or subsequence ordering, then Higman's Lemma ...
• 278k
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 ...
• 163k

### 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 ...
• 31.2k
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 ...
• 278k

### 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 ...
• 163k
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 ...
• 608
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 ...
• 7,565