SPOJ NSUBSTR Editorial

In the NSUBSTR problem on SPOJ, we are given a string $$$s$$$ of length $$$n$$$, and for every $$$k = 1$$$ to $$$n$$$, we are asked to find the maximum number of times any substring of length $$$k$$$ appears in $$$s$$$ (including overlapping occurrences).

1. Rephrasing the Problem

We need to compute, for each possible substring length $$$k$$$, the highest frequency among all substrings of length $$$k$$$. For example, if $$$s = "ababab"$$$:

$$$k=1$$$: substrings are {"a", "b"}, frequencies {3,3} → answer 3.
$$$k=2$$$: substrings are {"ab", "ba"}, frequencies {3,2} → answer 3.
etc.

A brute-force sliding-window plus hashing approach would be $$$O(n^2)$$$ or worse, which is too slow for $$$n$$$ up to $$$10^5$$$.

2. Key Insight: Suffix Array + LCP

We transform the problem into counting identical substrings by sorting all suffixes and using their common prefixes.

Suffix Array: an array $$$sa$$$ of length $n$ that lists the starting positions of all suffixes of $s$ in lexicographical order.
LCP Array: an array $$$lcp$$$ of length $n-1$ where $$$lcp[i]$$$ = length of the longest common prefix of the suffixes starting at $$$sa[i]$$$ and $$$sa[i+1]$$$.

Once we have $$$sa$$$ and $$$lcp$$$, any group of $$$c$$$ consecutive suffixes in sorted order share a common prefix of length at least $$$L = \min(lcp[i..i+c-2])$$$. That prefix corresponds to some substring of length $L$ occurring $$$c$$$ times.

3. From LCP to Maximum Frequencies

Let’s imagine the $$$lcp$$$ array as heights of bars in a histogram of size $$$n-1$$$. For each index $$$i$$$:

The bar at $$$i$$$ has height $$$h = lcp[i]$$$.
We want to know the largest span $$$[L[i], R[i]]$$$ around $$$i$$$ where all bars are at least height $h$.
That span corresponds to $$$c = (R[i] - L[i] + 2)$$$ suffixes sharing a common prefix of length $$$h$$$.

So for each $$$i$$$, we can update:

$$$ ans[h] = \max(ans[h], c) \quad\text{where } c = R[i]-L[i]+2. $$$

After processing all $$$i$$$, we have for each exact length $$$h$$$ the maximum count of some substring of length $$$h$$$. However, note that if a substring of length $$$h$$$ appears $$$c$$$ times, then all its prefixes (length $$$ \lt h$$$) appear at least $$$c$$$ times. Thus we perform a final pass:

$$$ \text{for } x = n-1 \downarrow 1:\quad ans[x] = \max(ans[x], ans[x+1]). $$$

This ensures the answer is non-decreasing as substring length shrinks.

4. Efficient Computation of $$$L[i], R[i]$$$

To find, for each bar $$$i$$$, the next smaller element on the left and right, we use a classic monotonic stack in two passes:

Left pass: iterate $$$i=0$$$ to $$$n-2$$$, maintain a stack of indices with strictly increasing $$$lcp$$$ heights. When $$$lcp[stack.top()] \ge lcp[i]$$$, pop. Then:

If stack empty, set $$$L[i]=0$$$; else $$$L[i]=stack.top()+1$$$.
Push $$$i$$$.

Right pass: similarly from $$$i=n-2$$$ down to 0, find next smaller on the right and set:

If stack empty, $$$R[i]=n-2$$$; else $$$R[i]=stack.top()-1$$$.

Each index is pushed/popped at most once ⇒ $$$O(n)$$$ total.

5. Putting It All Together

Optimal C++ Solution

#include <bits/stdc++.h>

std::vector<int> sa_naive(const std::vector<int>& s) {
    int n = int(s.size());
    std::vector<int> sa(n);
    std::iota(sa.begin(), sa.end(), 0);
    std::sort(sa.begin(), sa.end(), [&](int l, int r) {
        if (l == r) return false;
        while (l < n && r < n) {
            if (s[l] != s[r]) return s[l] < s[r];
            l++;
            r++;
        }
        return l == n;
    });
    return sa;
}

std::vector<int> sa_doubling(const std::vector<int>& s) {
    int n = int(s.size());
    std::vector<int> sa(n), rnk = s, tmp(n);
    std::iota(sa.begin(), sa.end(), 0);
    for (int k = 1; k < n; k *= 2) {
        auto cmp = [&](int x, int y) {
            if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
            int rx = x + k < n ? rnk[x + k] : -1;
            int ry = y + k < n ? rnk[y + k] : -1;
            return rx < ry;
        };
        std::sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        }
        std::swap(tmp, rnk);
    }
    return sa;
}

template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
    int n = int(s.size());
    if (n == 0) return {};
    if (n == 1) return {0};
    if (n == 2) {
        if (s[0] < s[1]) {
            return {0, 1};
        } else {
            return {1, 0};
        }
    }
    if (n < THRESHOLD_NAIVE) {
        return sa_naive(s);
    }
    if (n < THRESHOLD_DOUBLING) {
        return sa_doubling(s);
    }

    std::vector<int> sa(n);
    std::vector<bool> ls(n);
    for (int i = n - 2; i >= 0; i--) {
        ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
    }
    std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
    for (int i = 0; i < n; i++) {
        if (!ls[i]) {
            sum_s[s[i]]++;
        } else {
            sum_l[s[i] + 1]++;
        }
    }
    for (int i = 0; i <= upper; i++) {
        sum_s[i] += sum_l[i];
        if (i < upper) sum_l[i + 1] += sum_s[i];
    }

    auto induce = [&](const std::vector<int>& lms) {
        std::fill(sa.begin(), sa.end(), -1);
        std::vector<int> buf(upper + 1);
        std::copy(sum_s.begin(), sum_s.end(), buf.begin());
        for (auto d : lms) {
            if (d == n) continue;
            sa[buf[s[d]]++] = d;
        }
        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        sa[buf[s[n - 1]]++] = n - 1;
        for (int i = 0; i < n; i++) {
            int v = sa[i];
            if (v >= 1 && !ls[v - 1]) {
                sa[buf[s[v - 1]]++] = v - 1;
            }
        }
        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        for (int i = n - 1; i >= 0; i--) {
            int v = sa[i];
            if (v >= 1 && ls[v - 1]) {
                sa[--buf[s[v - 1] + 1]] = v - 1;
            }
        }
    };

    std::vector<int> lms_map(n + 1, -1);
    int m = 0;
    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms_map[i] = m++;
        }
    }
    std::vector<int> lms;
    lms.reserve(m);
    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms.push_back(i);
        }
    }

    induce(lms);

    if (m) {
        std::vector<int> sorted_lms;
        sorted_lms.reserve(m);
        for (int v : sa) {
            if (lms_map[v] != -1) sorted_lms.push_back(v);
        }
        std::vector<int> rec_s(m);
        int rec_upper = 0;
        rec_s[lms_map[sorted_lms[0]]] = 0;
        for (int i = 1; i < m; i++) {
            int l = sorted_lms[i - 1], r = sorted_lms[i];
            int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
            int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
            bool same = true;
            if (end_l - l != end_r - r) {
                same = false;
            } else {
                while (l < end_l) {
                    if (s[l] != s[r]) {
                        break;
                    }
                    l++;
                    r++;
                }
                if (l == n || s[l] != s[r]) same = false;
            }
            if (!same) rec_upper++;
            rec_s[lms_map[sorted_lms[i]]] = rec_upper;
        }

        auto rec_sa =
            sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);

        for (int i = 0; i < m; i++) {
            sorted_lms[i] = lms[rec_sa[i]];
        }
        induce(sorted_lms);
    }
    return sa;
}

std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
    assert(0 <= upper);
    for (int d : s) {
        assert(0 <= d && d <= upper);
    }
    auto sa = sa_is(s, upper);
    return sa;
}

template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
    int n = int(s.size());
    std::vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
    std::vector<int> s2(n);
    int now = 0;
    for (int i = 0; i < n; i++) {
        if (i && s[idx[i - 1]] != s[idx[i]]) now++;
        s2[idx[i]] = now;
    }
    return sa_is(s2, now);
}

std::vector<int> suffix_array(const std::string& s) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return sa_is(s2, 255);
}

template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
                           const std::vector<int>& sa) {
    assert(s.size() == sa.size());
    int n = int(s.size());
    assert(n >= 1);
    std::vector<int> rnk(n);
    for (int i = 0; i < n; i++) {
        assert(0 <= sa[i] && sa[i] < n);
        rnk[sa[i]] = i;
    }
    std::vector<int> lcp(n - 1);
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (h > 0) h--;
        if (rnk[i] == 0) continue;
        int j = sa[rnk[i] - 1];
        for (; j + h < n && i + h < n; h++) {
            if (s[j + h] != s[i + h]) break;
        }
        lcp[rnk[i] - 1] = h;
    }
    return lcp;
}

std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return lcp_array(s2, sa);
}

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    auto sa = suffix_array(s);
    auto lcp = lcp_array(s, sa);
    vector<int> L(n-1), R(n-1);
    stack<int> st;
    for(int i=0;i<n-1;i++){
        while(!st.empty() && lcp[st.top()]>=lcp[i]) st.pop();
        L[i] = st.empty() ? 0 : st.top()+1;
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i=n-2;i>=0;i--){
        while(!st.empty() && lcp[st.top()]>=lcp[i]) st.pop();
        R[i] = st.empty() ? (n-2) : (st.top()-1);
        st.push(i);
    }
    vector<int> ans(n+1,1);
    for(int i=0;i<n-1;i++){
        int h = lcp[i];
        int occ = R[i] - L[i] + 2;
        ans[h] = max(ans[h], occ);
    }
    for(int x=n-1;x>=1;x--) ans[x] = max(ans[x], ans[x+1]);
    for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
    return 0;
}

6. Suffix Array & LCP: A Quick Primer

Suffix Array in $$$O(n\log n)$$$: sort cyclic shifts by doubling technique (or SA-IS in $$$O(n)$$$).
LCP Array in $$$O(n)$$$ with Kasai’s algorithm: scans adjacent suffixes, reuses previous LCP to avoid recomputation.

If you’re unfamiliar, many tutorials walk through building suffix arrays by sorting starting characters, then doubling the length each round, reassigning classes.

7. Complexity

Building SA: $$$O(n\log n)$$$
Building LCP: $$$O(n)$$$
Two stack passes: $$$O(n)$$$
Final propagation & output: $$$O(n)$$$

Overall: $$$O(n\log n)$$$, suitable for $$$n$$$ up to $$$10^5$$$.

8. Conclusion

By reducing the substring-frequency problem to histogram spans over the LCP array, we elegantly count the maximum occurrences of each length in $$$O(n\log n)$$$. This approach highlights the power of suffix arrays and range queries with stacks for common-prefix problems.

	Rev.	Lang.	By	When	Δ	Comment
	en2		SydneySweeneyFan	2025-06-19 12:16:52	230
	en1		SydneySweeneyFan	2025-06-19 12:15:19	11605	Initial revision (published)

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133