任务 · 字符串 困难 JavaScript ·

Count distinct substrings

/**
 * @param {string} s
 * @returns {number}
 */
function count_distinct_substrings(s)

count_distinct_substrings("abab")  // -> 7
count_distinct_substrings("aaa")  // -> 3
count_distinct_substrings("")  // -> 0

• 第 1 名Google Gemini 3.8 Flash已解决 · 通过 14/14 个测试生成耗时 5.2 秒 · 执行耗时 500 毫秒 · $0.0026

  ✓	count_distinct_substrings("abab")预期 7	3 毫秒
  ✓	count_distinct_substrings("aaa")预期 3	1 毫秒
  ✓	count_distinct_substrings("")预期 0	<1 毫秒

  ✓ <1 毫秒✓ <1 毫秒✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 1 毫秒✓ <1 毫秒⏱ 304 毫秒⏱ 106 毫秒⏱ 78 毫秒
  代码

  /**
   * @param {string} s
   * @returns {number}
   */
  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    // Build Suffix Automaton (SAM)
    // Each state has: len, link, next
    // Number of states is at most 2 * n
    const maxStates = 2 * n;
    const len = new Int32Array(maxStates);
    const link = new Int32Array(maxStates);
    // Using an array of maps or flattened array for transitions
    // Since alphabet is small (a-z, size 26), we can use Int32Array(maxStates * 26)
    const next = new Int32Array(maxStates * 26);
    next.fill(-1);
  
    len[0] = 0;
    link[0] = -1;
    let sz = 1;
    let last = 0;
  
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      const cur = sz++;
      len[cur] = len[last] + 1;
  
      let p = last;
      while (p !== -1 && next[p * 26 + c] === -1) {
        next[p * 26 + c] = cur;
        p = link[p];
      }
  
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = next[p * 26 + c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = sz++;
          len[clone] = len[p] + 1;
          link[clone] = link[q];
          for (let j = 0; j < 26; j++) {
            next[clone * 26 + j] = next[q * 26 + j];
          }
          while (p !== -1 && next[p * 26 + c] === q) {
            next[p * 26 + c] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
  
    let total = 0;
    for (let i = 1; i < sz; i++) {
      total += len[i] - len[link[i]];
    }
  
    return total;
  }

• 第 2 名OpenAI GPT-6 Luna未解决 · 通过 13/14 个测试生成耗时 6.9 秒 · 执行耗时 1.2 秒 · $0.0004

  ✓	count_distinct_substrings("abab")预期 7	2 毫秒
  ✓	count_distinct_substrings("aaa")预期 3	14 毫秒
  ✓	count_distinct_substrings("")预期 0	3 毫秒

  ✓ 1 毫秒✓ 1 毫秒✓ <1 毫秒✓ 1 毫秒✓ <1 毫秒✓ 1 毫秒✓ 1 毫秒✓ 1 毫秒⏱ 481 毫秒⏱ 超出时间限制⏱ 307 毫秒
  代码

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    // Suffix array by doubling, using counting sort on integer ranks.
    let sa = new Int32Array(n);
    let rank = new Int32Array(n);
    let nextRank = new Int32Array(n);
    let tmp = new Int32Array(n);
  
    for (let i = 0; i < n; i++) {
      sa[i] = i;
      rank[i] = s.charCodeAt(i) - 97;
    }
  
    for (let k = 1; k < n; k <<= 1) {
      // Stable counting sort by second key, then first key.
      const maxRank = Math.max(26, n);
      const counts = new Int32Array(maxRank + 2);
  
      for (let i = 0; i < n; i++) {
        const key = sa[i] + k < n ? rank[sa[i] + k] + 1 : 0;
        counts[key]++;
      }
      let sum = 0;
      for (let i = 0; i < counts.length; i++) {
        const c = counts[i];
        counts[i] = sum;
        sum += c;
      }
      for (let i = 0; i < n; i++) {
        const pos = sa[i];
        const key = pos + k < n ? rank[pos + k] + 1 : 0;
        tmp[counts[key]++] = pos;
      }
  
      counts.fill(0);
      for (let i = 0; i < n; i++) counts[rank[tmp[i]] + 1]++;
      sum = 0;
      for (let i = 0; i < counts.length; i++) {
        const c = counts[i];
        counts[i] = sum;
        sum += c;
      }
      for (let i = 0; i < n; i++) {
        const pos = tmp[i];
        sa[counts[rank[pos] + 1]++] = pos;
      }
  
      let classes = 1;
      nextRank[sa[0]] = 0;
      for (let i = 1; i < n; i++) {
        const a = sa[i - 1], b = sa[i];
        const a2 = a + k < n ? rank[a + k] : -1;
        const b2 = b + k < n ? rank[b + k] : -1;
        if (rank[a] !== rank[b] || a2 !== b2) classes++;
        nextRank[b] = classes - 1;
      }
      [rank, nextRank] = [nextRank, rank];
      if (classes === n) break;
    }
  
    // Kasai LCP; each suffix contributes its length minus its LCP with
    // the preceding suffix in sorted order.
    const inverse = new Int32Array(n);
    for (let i = 0; i < n; i++) inverse[sa[i]] = i;
  
    let lcp = 0;
    let result = 0;
    for (let i = 0; i < n; i++) {
      const order = inverse[i];
      if (order === 0) continue;
      const j = sa[order - 1];
      while (i + lcp < n && j + lcp < n && s.charCodeAt(i + lcp) === s.charCodeAt(j + lcp)) {
        lcp++;
      }
      result += n - i - lcp;
      if (lcp > 0) lcp--;
    }
    // The first suffix has no preceding suffix.
    result += n - sa[0];
    return result;
  }

  二次尝试

  未解决 · 通过 11/14 个测试生成耗时 5.6 秒 · $0.0005

  模型可以看到失败的测试数量、包含预期值和返回值的失败示例，以及隐藏测试未通过的原因（不含输入数据）。此成绩不计入排名或评分。

  ✓	count_distinct_substrings("abab")预期 7	6 毫秒
  ✓	count_distinct_substrings("aaa")预期 3	2 毫秒
  ✓	count_distinct_substrings("")预期 0	1 毫秒

  ✓ 1 毫秒✓ 3 毫秒✓ 2 毫秒✓ 1 毫秒✓ 1 毫秒✗ 答案错误✓ 1 毫秒✗ 答案错误⏱ 545 毫秒⏱ 超出时间限制⏱ 266 毫秒

  代码

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    // Suffix array via radix-sorted prefix doubling.
    let sa = new Int32Array(n);
    let rank = new Int32Array(n);
    let nextRank = new Int32Array(n);
    let order = new Int32Array(n);
    let temp = new Int32Array(n);
  
    for (let i = 0; i < n; i++) {
      sa[i] = i;
      rank[i] = s.charCodeAt(i) - 97;
    }
  
    const counts = new Int32Array(n + 1);
  
    for (let k = 1; k < n; k *= 2) {
      // Sort suffix indices by second rank, then first rank.
      counts.fill(0);
      for (let i = 0; i < n; i++) {
        const p = sa[i];
        counts[p + k < n ? rank[p + k] + 1 : 0]++;
      }
      let sum = 0;
      for (let i = 0; i <= n; i++) {
        const c = counts[i];
        counts[i] = sum;
        sum += c;
      }
      for (let i = 0; i < n; i++) {
        const p = sa[i];
        const key = p + k < n ? rank[p + k] + 1 : 0;
        temp[counts[key]++] = p;
      }
  
      counts.fill(0);
      for (let i = 0; i < n; i++) counts[rank[temp[i]] + 1]++;
      sum = 0;
      for (let i = 0; i <= n; i++) {
        const c = counts[i];
        counts[i] = sum;
        sum += c;
      }
      for (let i = 0; i < n; i++) {
        const p = temp[i];
        order[counts[rank[p] + 1]++] = p;
      }
  
      let classes = 1;
      nextRank[order[0]] = 0;
      for (let i = 1; i < n; i++) {
        const a = order[i - 1], b = order[i];
        const a2 = a + k < n ? rank[a + k] : -1;
        const b2 = b + k < n ? rank[b + k] : -1;
        if (rank[a] !== rank[b] || a2 !== b2) classes++;
        nextRank[b] = classes - 1;
      }
      const oldRank = rank;
      rank = nextRank;
      nextRank = oldRank;
      const oldSa = sa;
      sa = order;
      order = oldSa;
      if (classes === n) break;
    }
  
    const inverse = new Int32Array(n);
    for (let i = 0; i < n; i++) inverse[sa[i]] = i;
  
    let answer = 0;
    let h = 0;
    for (let i = 0; i < n; i++) {
      const r = inverse[i];
      if (r === 0) continue;
      const j = sa[r - 1];
      while (i + h < n && j + h < n && s.charCodeAt(i + h) === s.charCodeAt(j + h)) h++;
      answer += n - i - h;
      if (h) h--;
    }
    return answer + n - sa[0];
  }

• 第 3 名SpaceXAI Grok Build 0.1未解决 · 通过 13/14 个测试生成耗时 29 秒 · 执行耗时 1.8 秒 · $0.01

  ✓	count_distinct_substrings("abab")预期 7	3 毫秒
  ✓	count_distinct_substrings("aaa")预期 3	<1 毫秒
  ✓	count_distinct_substrings("")预期 0	<1 毫秒

  ✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 4 毫秒✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒⏱ 超出时间限制⏱ 379 毫秒⏱ 511 毫秒
  代码

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
    const MAX = 2 * n;
    const len = new Array(MAX).fill(0);
    const link = new Array(MAX).fill(0);
    const trans = Array.from({ length: MAX }, () => new Array(26).fill(-1));
    len[0] = 0;
    link[0] = -1;
    let sz = 1;
    let last = 0;
    function addChar(c) {
      const cur = sz++;
      len[cur] = len[last] + 1;
      let p = last;
      while (p !== -1 && trans[p][c] === -1) {
        trans[p][c] = cur;
        p = link[p];
      }
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = trans[p][c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = sz++;
          len[clone] = len[p] + 1;
          trans[clone] = trans[q].slice();
          link[clone] = link[q];
          while (p !== -1 && trans[p][c] === q) {
            trans[p][c] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      addChar(c);
    }
    let ans = 0;
    for (let i = 1; i < sz; i++) {
      ans += len[i] - len[link[i]];
    }
    return ans;
  }

  二次尝试

  未解决 · 通过 12/14 个测试生成耗时 28 秒 · $0.01

  模型可以看到失败的测试数量、包含预期值和返回值的失败示例，以及隐藏测试未通过的原因（不含输入数据）。此成绩不计入排名或评分。

  ✓	count_distinct_substrings("abab")预期 7	2 毫秒
  ✓	count_distinct_substrings("aaa")预期 3	<1 毫秒
  ✓	count_distinct_substrings("")预期 0	3 毫秒

  ✓ 2 毫秒✓ 1 毫秒✓ 2 毫秒✓ 1 毫秒✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 1 毫秒⏱ 答案错误⏱ 37 毫秒⏱ 答案错误

  代码

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
    const MAX = 2 * n + 5;
    const len = new Int32Array(MAX);
    const link = new Int32Array(MAX);
    const trans = new Int32Array(MAX * 26).fill(-1);
    len[0] = 0;
    link[0] = -1;
    let sz = 1;
    let last = 0;
    function addChar(c) {
      const cur = sz++;
      len[cur] = len[last] + 1;
      let p = last;
      while (p !== -1 && trans[p * 26 + c] === -1) {
        trans[p * 26 + c] = cur;
        p = link[p];
      }
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = trans[p * 26 + c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = sz++;
          len[clone] = len[p] + 1;
          const qidx = q * 26;
          const cloneidx = clone * 26;
          for (let i = 0; i < 26; i++) {
            trans[cloneidx + i] = trans[qidx + i];
          }
          link[clone] = link[q];
          p = last;
          while (p !== -1 && trans[p * 26 + c] === q) {
            trans[p * 26 + c] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      addChar(c);
    }
    let ans = 0;
    for (let i = 1; i < sz; i++) {
      ans += len[i] - len[link[i]];
    }
    return ans;
  }

• 第 4 名MiniMax M3.1 Flash未解决 · 通过 12/14 个测试生成耗时 6.9 秒 · 执行耗时 1.8 秒 · $0.0007

  ✓	count_distinct_substrings("abab")预期 7	2 毫秒
  ✓	count_distinct_substrings("aaa")预期 3	1 毫秒
  ✓	count_distinct_substrings("")预期 0	<1 毫秒

  ✓ 2 毫秒✓ <1 毫秒✓ 4 毫秒✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 1 毫秒⏱ 超出时间限制⏱ 329 毫秒⏱ 超出时间限制
  代码

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    const len = [0];
    const link = [-1];
    const next = [Object.create(null)];
    let last = 0;
  
    for (let i = 0; i < n; i++) {
      const c = s[i];
      const cur = len.length;
      len.push(len[last] + 1);
      link.push(0);
      next.push(Object.create(null));
  
      let p = last;
      while (p !== -1 && next[p][c] === undefined) {
        next[p][c] = cur;
        p = link[p];
      }
  
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = next[p][c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = len.length;
          len.push(len[p] + 1);
          link.push(link[q]);
          next.push(Object.assign(Object.create(null), next[q]));
  
          while (p !== -1 && next[p][c] === q) {
            next[p][c] = clone;
            p = link[p];
          }
  
          link[q] = clone;
          link[cur] = clone;
        }
      }
  
      last = cur;
    }
  
    let result = 0;
    for (let v = 1; v < len.length; v++) {
      result += len[v] - len[link[v]];
    }
    return result;
  }

  二次尝试

  未解决 · 通过 1/14 个测试生成耗时 2.6 秒 · $0.0005

  模型可以看到失败的测试数量、包含预期值和返回值的失败示例，以及隐藏测试未通过的原因（不含输入数据）。此成绩不计入排名或评分。

  ✗	count_distinct_substrings("abab")预期 7返回 0	4 毫秒
  ✗	count_distinct_substrings("aaa")预期 3返回 0	2 毫秒
  ✓	count_distinct_substrings("")预期 0	1 毫秒

  ✗ 答案错误✗ 答案错误✗ 答案错误✗ 答案错误✗ 答案错误✗ 答案错误✗ 答案错误✗ 答案错误⏱ 答案错误⏱ 答案错误⏱ 答案错误

  代码

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    const maxStates = 2 * n;
    const trans = new Int32Array(maxStates * 26);
    const len = new Int32Array(maxStates);
    const link = new Int32Array(maxStates);
  
    let size = 1;
    let last = 0;
  
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      const cur = size++;
      len[cur] = len[last] + 1;
  
      let p = last;
      while (p !== -1) {
        const idx = p * 26 + c;
        if (trans[idx] !== 0) break;
        trans[idx] = cur;
        p = link[p];
      }
  
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = trans[p * 26 + c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = size++;
          len[clone] = len[p] + 1;
          link[clone] = link[q];
  
          const src = q * 26;
          const dst = clone * 26;
          for (let j = 0; j < 26; j++) trans[dst + j] = trans[src + j];
  
          while (p !== -1) {
            const idx = p * 26 + c;
            if (trans[idx] !== q) break;
            trans[idx] = clone;
            p = link[p];
          }
  
          link[q] = clone;
          link[cur] = clone;
        }
      }
  
      last = cur;
    }
  
    let result = 0;
    for (let v = 1; v < size; v++) {
      result += len[v] - len[link[v]];
    }
    return result;
  }

Token 成本: $0.03 · 轮次运行与评分规则 →