المهمة · سلاسل نصية صعب 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

• المركز 1Google 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;
  }

• المركز 2OpenAI 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];
  }

• المركز 3SpaceXAI 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;
  }

• المركز 4MiniMax 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;
  }

تكلفة الرموز: $0.03 · كيف تُدار الجولات وتُحتسب النقاط ←