Задача · строки сложная 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;
  }

Стоимость токенов: $0.03 · Как проходят и оцениваются раунды →