KMR Algorithm

Purpose: Karp-Miller-Rosenberg (1972) — the prefix doubling technique. Assign a canonical integer name to every substring of length $2^k$, for every $k$, in $O(n\log n)$ total. This single idea underlies suffix array construction, string comparison in $O(1)$, and a whole family of string DP tricks.

Algorithm

Let ${\mathrm{id}}_k[i]$ be the class label of the substring s[i .. i+2^k).

1. ${\mathrm{id}}_0[i]$ = the character s[i] (or its rank in the alphabet).
2. For each $k$: form the pair
   $({\mathrm{id}}_k[i],{\mathrm{id}}_k[i+2^k])$
   for every $i$, sort the pairs (radix sort in $O(n)$), and let ${\mathrm{id}}_{k+1}[i]$ be the rank of $i$‘s pair. Two positions get the same label iff their length-$2^{k+1}$ substrings are identical.
3. Stop after $\lceil {\log }_{2}n\rceil$ rounds.

Code

// id[k][i] = class of s[i .. i+2^k), for all k. O(n log n) time and memory.
vector<vector<int>> kmr(const string& s) {
    int n = s.size(), LOG = 1;
    while ((1 << LOG) < n) LOG++;
    vector<vector<int>> id(LOG + 1, vector<int>(n));
 
    {   // level 0
        vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int a, int b){ return s[a] < s[b]; });
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (i && s[ord[i]] != s[ord[i-1]]) c++;
            id[0][ord[i]] = c;
        }
    }
 
    for (int k = 0; k < LOG; k++) {
        int len = 1 << k;
        vector<pair<pair<int,int>,int>> a(n);
        for (int i = 0; i < n; i++)
            a[i] = {{id[k][i], i + len < n ? id[k][i + len] : -1}, i};
        sort(a.begin(), a.end());
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (i && a[i].first != a[i-1].first) c++;
            id[k+1][a[i].second] = c;
        }
    }
    return id;
}

Complexity

• Time: $O(n\log n)$ with radix sort per level, $O(n{\log }^{2}n)$ with std::sort
• Space: $O(n\log n)$ if you keep every level; $O(n)$ if you only need the last

What the table buys you

Once id[][] exists, compare any two substrings of equal length in $O(1)$: split the length into two overlapping powers of two,

$\text{s[i..i+L)}=\text{s[j..j+L)}⟺{\mathrm{id}}_k[i]={\mathrm{id}}_k[j]\wedge {\mathrm{id}}_k[i+L-2^k]={\mathrm{id}}_k[j+L-2^k]$

with $k=\lfloor {\log }_{2}L\rfloor$. This is a deterministic alternative to string hashing — no collision risk, no anti-hash tests, at the cost of $O(n\log n)$ memory.

Variants / Use Cases

• Suffix array construction — prefix doubling is KMR; the suffix array is just the final ordering
• $O(1)$ substring comparison — for suffix ordering, lexicographic DP, and canonical forms without hashing
• Longest common extension (LCE) — binary search on length using $O(1)$ equality tests, giving $O(\log n)$ LCE
• Tandem repeats and periodicity queries
• SA-IS — the $O(n)$ alternative when $n\log n$ memory is too much
• Hashing — the randomised competitor: $O(n)$ memory, $O(1)$ compare, small failure probability