โจทย์ · สตริง ยาก 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 มิลลิวินาที · $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;
  }

• อันดับ #2Google 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;
  }

• อันดับ #3Qwen3.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;
  }

• อันดับ #4SpaceXAI 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;
  }

ค่าใช้จ่ายโทเค็น: $0.05 · วิธีจัดการแข่งขันและการคิดคะแนน →