如何以更低时间复杂度统计字符串所有子串的出现次数？

Great question! Your current two-loop approach gets the job done, but as you’ve noticed, its O(N²) time and space complexity can become a real bottleneck for longer strings. Let’s dig into better alternatives.

First, Let’s Break Down Your Current Code #

Your implementation iterates over every possible starting index j, then grabs every possible substring length starting at that index via i. Using a Map to track counts is straightforward—but since there are O(N²) total substrings in a string of length N, this approach will slow down dramatically as N grows (e.g., N=1000 would mean 500k+ substrings to process). For short strings, this is totally fine, but it doesn’t scale well.

The Most Efficient Solution: Suffix Automaton #

The fastest way to solve this problem is using a Suffix Automaton (SAM). This data structure can be built in O(N) time and space, and lets us count all distinct substring frequencies in an additional O(N) time.

Here’s a quick breakdown of how it works:

• A SAM compresses all substrings of a string into states. Each state represents a group of substrings that end at the same positions (called an endpos set).
• Each state stores:
  • len: The maximum length of substrings in the state
  • link: A pointer to a "suffix state" (for grouping related substrings)
  • count: The number of times the substrings in this state appear
• After building the SAM, we sort states by length (topological order) and propagate counts through suffix links to get total occurrences for each substring group.
• Finally, we can iterate through states to extract all distinct substrings and their frequencies.

Simplified JavaScript Implementation #

Here’s a working SAM implementation tailored to your problem:

class State {
  constructor() {
    this.len = 0;
    this.link = -1;
    this.next = new Map();
    this.count = 0;
  }
}

function countSubstringFrequencies(s) {
  const sa = [new State()];
  let last = 0;
  sa[0].count = 1;

  // Build the suffix automaton
  for (const c of s) {
    let curr = sa.length;
    sa.push(new State());
    sa[curr].len = sa[last].len + 1;
    sa[curr].count = 1;
    let p = last;

    while (p !== -1 && !sa[p].next.has(c)) {
      sa[p].next.set(c, curr);
      p = sa[p].link;
    }

    if (p === -1) {
      sa[curr].link = 0;
    } else {
      let q = sa[p].next.get(c);
      if (sa[p].len + 1 === sa[q].len) {
        sa[curr].link = q;
      } else {
        let clone = sa.length;
        sa.push(new State());
        sa[clone].len = sa[p].len + 1;
        sa[clone].next = new Map(sa[q].next);
        sa[clone].link = sa[q].link;
        sa[clone].count = 0;

        while (p !== -1 && sa[p].next.get(c) === q) {
          sa[p].next.set(c, clone);
          p = sa[p].link;
        }
        sa[q].link = clone;
        sa[curr].link = clone;
      }
    }
    last = curr;
  }

  // Propagate counts via topological sort
  const sortedStates = sa.slice().sort((a, b) => b.len - a.len);
  for (const state of sortedStates) {
    if (state.link !== -1) {
      sa[state.link].count += state.count;
    }
  }

  // Collect all substrings and their frequencies
  const result = new Map();
  function dfs(state, currentStr) {
    if (state.len > 0) {
      const startLen = state.link === -1 ? 0 : sa[state.link].len;
      for (let l = startLen + 1; l <= state.len; l++) {
        const substr = currentStr.slice(currentStr.length - l);
        result.set(substr, state.count);
      }
    }
    for (const [char, nextIdx] of state.next) {
      dfs(sa[nextIdx], currentStr + char);
    }
  }
  dfs(sa[0], "");
  return result;
}

// Test with your input string
const myString = 'dgfdgwababccgregabcaavbrabcrafsfabcdsdsfhjuuyiuyuitrerttfvbcvretrcw';
const freqMap = countSubstringFrequencies(myString);

for (const [key, value] of freqMap) {
  console.log(`${key} = ${value}`);
}

Key Notes #

• The SAM building step runs in O(N) time, no matter the string content.
• The final DFS to list all substrings takes O(D) time, where D is the number of distinct substrings. For strings with repeated patterns (like your example), D is way smaller than O(N²). If you don’t need to list every substring explicitly, you can skip the DFS and work directly with state ranges.

Other Alternatives #

If SAM feels too complex, you could use a Suffix Array paired with an LCP (Longest Common Prefix) array, but this requires more auxiliary processing. Suffix Trees are another option, but their implementation is more verbose than SAM.

When to Keep Your Original Code #

If you’re only working with very short strings (e.g., N < 1000), your O(N²) method is totally acceptable—it’s simple to read and maintain. But for longer strings, SAM is the clear performance winner.

内容的提问来源于stack exchange，提问作者Zlil Korman