Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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 ...
JounceCracklePop's 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 ...
Pseudonym's user avatar
  • 22.2k
16 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, ...
John L.'s user avatar
  • 39k
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 ...
Yuval Filmus's 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 ...
D.W.'s user avatar
  • 160k
11 votes
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)$ ...
Nathaniel's user avatar
  • 15.7k
10 votes
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 ...
Yuval Filmus's 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 ...
D.W.'s user avatar
  • 160k
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 ...
gnasher729's user avatar
  • 30.4k
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 ...
Yuval Filmus's 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 ...
D.W.'s user avatar
  • 160k
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 ...
Bergi's user avatar
  • 608
7 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 ...
xskxzr's user avatar
  • 7,455
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 ...
Yuval Filmus's 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 ...
Riley's user avatar
  • 280
6 votes
Accepted

Why does little endian apply to numbers and not to text strings?

The premise is wrong. Unicode encodings include UTF-16BE, UTF-16LE, UTF-32BE and UTF32-LE. Only UTF-8 has no Litte-Endian or Big-Endian variants. Fundamentally, Endian-ness is about the byte order of ...
MSalters's user avatar
  • 895
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 ...
D.W.'s user avatar
  • 160k
6 votes
Accepted

How many "compressible" strings are there?

A simple counting argument shows that the number of strings of length $N$ such that $K(S) \leq M$ is at most $2^{M+1}$. Conversely, considering the program $\Pi$ that gets an integer $r$ and a string ...
Yuval Filmus's user avatar
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 ...
pcpthm's user avatar
  • 2,393
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 $...
Yuval Filmus's user avatar
5 votes
Accepted

Space complexity of string indices: O(1) or O(log|S|)?

These are correct (unless you explicitly specify a non-standard model of computing): $O(1)$ space, $O(1)$ words of space, $O(\log|S|)$ bits of space.
Jukka Suomela's user avatar
5 votes

String matching algorithm - check if a string matches a pattern

There are various algorithms for pattern matching in string. Exact String matching algorithms Brute Force Rabin Karp Boyer-Moree KMP Aho Corasick etc. Approximate String Matching Algorithm ...
Anjo's user avatar
  • 372
5 votes
Accepted

Counting substrings with a given number of different characters in O(N)

You can solve this in $O(n)$ time using two (well, three) pointers that both move leftward. Let $S$ be the string. We'll let $i$ range from $n$ down to $1$, and for each value of $i$, we're going to ...
D.W.'s user avatar
  • 160k
5 votes
Accepted

Complexity of Block edit distance with Swapping only

When one operation is exactly "removing a block and inserting it between two other positions", the problem of computing the string distance is known as Transposition Distance. It is NP-hard even if ...
Christian Komusiewicz's user avatar
5 votes
Accepted

Algorithm: given very large file of strings, find lines containing substring

You can construct a suffix tree for that very large file and once generated the same can be used for querying. For Suffix tree generation use Suffix Array approach, there are many algorithm to ...
Chits's user avatar
  • 119
5 votes

I'm looking for an algorithm to find unknown patterns in a string

Construct the suffix tree of your string, which takes time linear in the length of the string (assuming a finite alphabet). Every inner node represents a repeat, their respective descendant leaves ...
Raphael's user avatar
  • 72.5k
5 votes
Accepted

Maximum number of different substrings in big string

Here is a general solution for an alphabet of size $d \geq 3$ and a string of length $n$. Every string of length $n$ has $n-\ell+1$ substrings of length $\ell$. Hence the number of different ...
Yuval Filmus's user avatar
5 votes

Algorithm to identify contiguous repeated series of lines in a long string

Build suffix tree using Ukkonen's algorithm, this way in $\mathcal O(n)$ you will find all substrings in provided text with indices. In the case of approximate matching, there is also extended ...
Evil's user avatar
  • 9,465
5 votes
Accepted

Algorithm to identify contiguous repeated series of lines in a long string

Under normal circumstances, JVM fills only the last 1024 calls in a stacktrace, and in Dotty/Scalac most stackoverflows have a repeating fragment of length ≈ 70 or less. A stacktrace T of a ...
hoopoefret's user avatar
5 votes
Accepted

Sampling a uniform distribution of fixed size strings containing no forbidden substrings

Suppose the alphabet is $\{a,b\}$, and you have one forbidden word, $aa$. Suppose we are trying to generate a word of length 3. The first two letters will be distributed uniformly over $ab,ba,bb$. ...
Yuval Filmus's user avatar

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