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

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