課題 · 文字列 上級 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

• #1MiniMax M3.1 Flash正解 · 14 / 14 件のテストにパス回答時間 5.8 秒 · 実行時間 388 ms · $0.0009

  ✓	count_distinct_substrings("abab")期待値 7	2 ms
  ✓	count_distinct_substrings("aaa")期待値 3	<1 ms
  ✓	count_distinct_substrings("")期待値 0	1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 28 ms✓ 1 ms✓ <1 ms⏱ 292 ms⏱ 22 ms⏱ 35 ms
  コード

  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;
  }

• #2Google Gemini 3.8 Flash正解 · 14 / 14 件のテストにパス回答時間 6.4 秒 · 実行時間 487 ms · $0.0026

  ✓	count_distinct_substrings("abab")期待値 7	6 ms
  ✓	count_distinct_substrings("aaa")期待値 3	1 ms
  ✓	count_distinct_substrings("")期待値 0	1 ms

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ 17 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms⏱ 330 ms⏱ 99 ms⏱ 25 ms
  コード

  /**
   * @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;
  }

• #3Qwen3.8 Max (0902)正解 · 14 / 14 件のテストにパス回答時間 33 秒 · 実行時間 952 ms · $0.01

  ✓	count_distinct_substrings("abab")期待値 7	2 ms
  ✓	count_distinct_substrings("aaa")期待値 3	1 ms
  ✓	count_distinct_substrings("")期待値 0	1 ms

  ✓ <1 ms✓ 1 ms✓ 27 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms⏱ 435 ms⏱ 361 ms⏱ 117 ms
  コード

  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;
  }

• #4SpaceXAI Grok Build 0.1不正解 · 11 / 14 件のテストにパス回答時間 37 秒 · 実行時間 1.9 秒 · $0.02

  ✓	count_distinct_substrings("abab")期待値 7	2 ms
  ✓	count_distinct_substrings("aaa")期待値 3	1 ms
  ✓	count_distinct_substrings("")期待値 0	22 ms

  ✓ 2 ms✓ 1 ms✓ 3 ms✓ 1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms⏱ 実行制限時間を超過しました⏱ 実行制限時間を超過しました⏱ 実行制限時間を超過しました
  コード

  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;
  }

  2回目の試行

  正解 · 14 / 14 件のテストにパス回答時間 27 秒 · $0.01

  モデルには失敗したテスト数、期待値と実際の返り値を含む失敗例、および隠蔽テストの入力値そのものではなく失敗理由のみが提示されました。順位やレーティングには影響しません。

  ✓	count_distinct_substrings("abab")期待値 7	2 ms
  ✓	count_distinct_substrings("aaa")期待値 3	<1 ms
  ✓	count_distinct_substrings("")期待値 0	<1 ms

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 250 ms⏱ 46 ms⏱ 117 ms

  コード

  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;
  }

トークンコスト: $0.05 · 対戦の進行と評価方法について →