任务 · 字符串困难 JavaScript ·

Count distinct substrings

Return the number of different non-empty substrings of s (contiguous pieces; equal pieces at different positions count once). s has lowercase letters only and can be up to 100,000 characters long.

函数签名

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

示例

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

另有 8 个隐藏测试和 3 个限时海量数据测试；其输入数据不公开。任务以英文提示词提供给模型。

第 1 名MiniMax M3.1 Flash已解决 · 通过 14/14 个测试生成耗时 5.8 秒 · 执行耗时 388 毫秒 · $0.0009

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

✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 2 毫秒✓ 28 毫秒✓ 1 毫秒✓ <1 毫秒⏱ 292 毫秒⏱ 22 毫秒⏱ 35 毫秒

代码

function count_distinct_substrings(s) {
  const n = s.length;
  if (n === 0) return 0;

  const maxStates = 2 * n + 1;
  const tr = new Int32Array(maxStates * 26);
  const len = new Int32Array(maxStates);
  const link = new Int32Array(maxStates);

  link[0] = -1;
  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 (tr[idx] !== 0) break;
      tr[idx] = cur;
      p = link[p];
    }

    if (p === -1) {
      link[cur] = 0;
    } else {
      const q = tr[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 cb = clone * 26, qb = q * 26;
        for (let k = 0; k < 26; k++) tr[cb + k] = tr[qb + k];
        while (p !== -1) {
          const idx = p * 26 + c;
          if (tr[idx] !== q) break;
          tr[idx] = clone;
          p = link[p];
        }
        link[q] = clone;
        link[cur] = clone;
      }
    }
    last = cur;
  }

  let total = 0;
  for (let v = 1; v < size; v++) total += len[v] - len[link[v]];
  return total;
}

第 2 名Google Gemini 3.8 Flash已解决 · 通过 14/14 个测试生成耗时 6.4 秒 · 执行耗时 487 毫秒 · $0.0026

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

✓ <1 毫秒✓ 1 毫秒✓ 1 毫秒✓ 17 毫秒✓ 2 毫秒✓ 1 毫秒✓ 1 毫秒✓ <1 毫秒⏱ 330 毫秒⏱ 99 毫秒⏱ 25 毫秒

代码

/**
 * @param {string} s
 * @returns {number}
 */
function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
    if (n === 1) return 1;

    // Suffix Automaton (SAM) approach
    // Max states: 2 * n
    const maxStates = 2 * n;
    const link = new Int32Array(maxStates);
    const len = new Int32Array(maxStates);
    // 26 transitions per state
    const nextState = new Int32Array(maxStates * 26);
    nextState.fill(-1);

    link[0] = -1;
    len[0] = 0;
    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 && nextState[p * 26 + c] === -1) {
            nextState[p * 26 + c] = cur;
            p = link[p];
        }

        if (p === -1) {
            link[cur] = 0;
        } else {
            const q = nextState[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];
                // copy transitions
                const qOffset = q * 26;
                const cloneOffset = clone * 26;
                for (let k = 0; k < 26; k++) {
                    nextState[cloneOffset + k] = nextState[qOffset + k];
                }

                while (p !== -1 && nextState[p * 26 + c] === q) {
                    nextState[p * 26 + c] = clone;
                    p = link[p];
                }
                link[q] = clone;
                link[cur] = clone;
            }
        }
        last = cur;
    }

    let ans = 0;
    for (let i = 1; i < sz; i++) {
        ans += len[i] - len[link[i]];
    }

    return ans;
}

第 3 名Qwen3.8 Max (0902)已解决 · 通过 14/14 个测试生成耗时 33 秒 · 执行耗时 952 毫秒 · $0.01

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

✓ <1 毫秒✓ 1 毫秒✓ 27 毫秒✓ 1 毫秒✓ <1 毫秒✓ 1 毫秒✓ 1 毫秒✓ <1 毫秒⏱ 435 毫秒⏱ 361 毫秒⏱ 117 毫秒

代码

function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
    
    // Build suffix array using prefix doubling
    let sa = new Array(n);
    let rank = new Array(n);
    let tmp = new Array(n);
    
    for (let i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s.charCodeAt(i);
    }
    
    for (let k = 1; k < n; k <<= 1) {
        const r = rank; // capture current rank
        const cmp = (a, b) => {
            if (r[a] !== r[b]) return r[a] - r[b];
            const ra = a + k < n ? r[a + k] : -1;
            const rb = b + k < n ? r[b + k] : -1;
            return ra - rb;
        };
        sa.sort(cmp);
        
        tmp[sa[0]] = 0;
        for (let i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) < 0 ? 1 : 0);
        }
        [rank, tmp] = [tmp, rank];
        
        if (rank[sa[n-1]] === n - 1) break;
    }
    
    // Kasai's algorithm for LCP array
    // rank[i] = position of suffix i in suffix array
    let lcpSum = 0;
    let h = 0;
    
    for (let i = 0; i < n; i++) {
        if (rank[i] > 0) {
            let j = sa[rank[i] - 1];
            while (i + h < n && j + h < n && s.charCodeAt(i + h) === s.charCodeAt(j + h)) h++;
            lcpSum += h;
            if (h > 0) h--;
        } else {
            h = 0;
        }
    }
    
    return n * (n + 1) / 2 - lcpSum;
}

第 4 名SpaceXAI Grok Build 0.1未解决 · 通过 11/14 个测试生成耗时 37 秒 · 执行耗时 1.9 秒 · $0.02

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

✓ 2 毫秒✓ 1 毫秒✓ 3 毫秒✓ 1 毫秒✓ <1 毫秒✓ 2 毫秒✓ 2 毫秒✓ 1 毫秒⏱ 超出时间限制⏱ 超出时间限制⏱ 超出时间限制

代码

function count_distinct_substrings(s) {
  const n = s.length;
  if (n === 0) return 0;
  const MAX = 2 * n + 10;
  const len = new Array(MAX);
  const link = new Array(MAX);
  const trans = new Array(MAX);
  for (let i = 0; i < MAX; i++) {
    trans[i] = new Array(26).fill(-1);
  }
  let tot = 1;
  len[0] = 0;
  link[0] = -1;
  let last = 0;
  for (let i = 0; i < n; i++) {
    const c = s.charCodeAt(i) - 97;
    let cur = tot++;
    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 {
      let q = trans[p][c];
      if (len[q] === len[p] + 1) {
        link[cur] = q;
      } else {
        let clone = tot++;
        len[clone] = len[p] + 1;
        link[clone] = link[q];
        for (let j = 0; j < 26; j++) {
          trans[clone][j] = trans[q][j];
        }
        while (p !== -1 && trans[p][c] === q) {
          trans[p][c] = clone;
          p = link[p];
        }
        link[q] = clone;
        link[cur] = clone;
      }
    }
    last = cur;
  }
  let count = 0;
  for (let i = 1; i < tot; i++) {
    count += len[i] - len[link[i]];
  }
  return count;
}

二次尝试

已解决 · 通过 14/14 个测试生成耗时 27 秒 · $0.01

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

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

✓ 1 毫秒✓ 2 毫秒✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 1 毫秒⏱ 250 毫秒⏱ 46 毫秒⏱ 117 毫秒

代码

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);
  trans.fill(-1);
  let tot = 1;
  len[0] = 0;
  link[0] = -1;
  let last = 0;
  for (let i = 0; i < n; i++) {
    const c = s.charCodeAt(i) - 97;
    let cur = tot++;
    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 {
      let q = trans[p * 26 + c];
      if (len[q] === len[p] + 1) {
        link[cur] = q;
      } else {
        let clone = tot++;
        len[clone] = len[p] + 1;
        link[clone] = link[q];
        const qbase = q * 26;
        const clonebase = clone * 26;
        for (let j = 0; j < 26; j++) {
          trans[clonebase + j] = trans[qbase + j];
        }
        while (p !== -1 && trans[p * 26 + c] === q) {
          trans[p * 26 + c] = clone;
          p = link[p];
        }
        link[q] = clone;
        link[cur] = clone;
      }
    }
    last = cur;
  }
  let count = 0;
  for (let i = 1; i < tot; i++) {
    count += len[i] - len[link[i]];
  }
  return count;
}

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