Завдання · рядки складний Python ·

Longest repeated substring

def longest_repeat(s: str) -> str:

longest_repeat('banana')  # -> 'ana'
longest_repeat('abcd')  # -> ''
longest_repeat('aaaa')  # -> 'aaa'

• #1OpenAI GPT-6.1 Terraрозв'язано · 15 з 15 тестіввідповідь за 6.0 с · виконання 932 мс · $0.0021

  ✓	longest_repeat('banana')очікувалося 'ana'	<1 мс
  ✓	longest_repeat('abcd')очікувалося ''	<1 мс
  ✓	longest_repeat('aaaa')очікувалося 'aaa'	<1 мс

  ✓ <1 мс✓ <1 мс✓ 2 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 449 мс⏱ 165 мс⏱ 310 мс
  Код

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
  
      transitions = [{}]
      links = [-1]
      lengths = [0]
      first_pos = [-1]
      last = 0
  
      for i, ch in enumerate(s):
          cur = len(links)
          transitions.append({})
          lengths.append(lengths[last] + 1)
          links.append(0)
          first_pos.append(i)
  
          p = last
          while p >= 0 and ch not in transitions[p]:
              transitions[p][ch] = cur
              p = links[p]
  
          if p >= 0:
              q = transitions[p][ch]
              if lengths[p] + 1 == lengths[q]:
                  links[cur] = q
              else:
                  clone = len(links)
                  transitions.append(transitions[q].copy())
                  lengths.append(lengths[p] + 1)
                  links.append(links[q])
                  first_pos.append(first_pos[q])
  
                  while p >= 0 and transitions[p].get(ch) == q:
                      transitions[p][ch] = clone
                      p = links[p]
  
                  links[q] = clone
                  links[cur] = clone
  
          last = cur
  
      best_len = 0
      best_start = n
      for state in range(1, len(links)):
          parent = links[state]
          length = lengths[parent]
          if length >= best_len and length:
              start = first_pos[parent] - length + 1
              if length > best_len or start < best_start:
                  best_len = length
                  best_start = start
  
      return s[best_start:best_start + best_len] if best_len else ""

• #2DeepSeek V4.1 Flashне розв'язано · 14 з 15 тестіввідповідь за 1.9 с · виконання 1.7 с · $0.0003

  ✓	longest_repeat('banana')очікувалося 'ana'	<1 мс
  ✓	longest_repeat('abcd')очікувалося ''	<1 мс
  ✓	longest_repeat('aaaa')очікувалося 'aaa'	<1 мс

  ✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ 2 мс✓ 1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 634 мс⏱ перевищено ліміт часу⏱ 529 мс
  Код

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n <= 1:
          return ""
      # build suffix array via prefix doubling
      sa = list(range(n))
      rank = [ord(c) for c in s]
      k = 1
      tmp = [0] * n
      while True:
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
          tmp[sa[0]] = 0
          for idx in range(1, n):
              a = sa[idx - 1]
              b = sa[idx]
              ra = rank[a]
              rb = rank[b]
              if ra != rb:
                  tmp[b] = tmp[a] + 1
              else:
                  ra2 = rank[a + k] if a + k < n else -1
                  rb2 = rank[b + k] if b + k < n else -1
                  tmp[b] = tmp[a] + (1 if ra2 != rb2 else 0)
          rank, tmp = tmp, rank
          if rank[sa[-1]] == n - 1:
              break
          k <<= 1
  
      # kasai LCP
      lcp = [0] * n
      p = [0] * n
      for i in range(n):
          p[sa[i]] = i
      h = 0
      for i in range(n):
          r = p[i]
          if r > 0:
              j = sa[r - 1]
              while i + h < n and j + h < n and s[i + h] == s[j + h]:
                  h += 1
              lcp[r] = h
              if h:
                  h -= 1
          else:
              h = 0
  
      best_len = 0
      best_pos = 0
      for r in range(1, n):
          l = lcp[r]
          if l > best_len:
              best_len = l
              best_pos = sa[r - 1] if sa[r - 1] < sa[r] else sa[r]
          elif l == best_len and l > 0:
              pos = sa[r - 1] if sa[r - 1] < sa[r] else sa[r]
              if pos < best_pos:
                  best_pos = pos
      return s[best_pos:best_pos + best_len] if best_len > 0 else ""

  Друга спроба

  не розв'язано · 14 з 15 тестіввідповідь за 2.0 с · $0.0006

  Модель бачила кількість невдалих тестів, приклади з очікуваними та отриманими значеннями, а для прихованих тестів — лише причину помилки без вхідних даних. Не враховується в рейтингу та місцях.

  ✓	longest_repeat('banana')очікувалося 'ana'	2 мс
  ✓	longest_repeat('abcd')очікувалося ''	<1 мс
  ✓	longest_repeat('aaaa')очікувалося 'aaa'	<1 мс

  ✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 825 мс⏱ перевищено ліміт часу⏱ 624 мс

  Код

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n <= 1:
          return ""
      
      # Build suffix array using prefix doubling with counting sort (radix sort)
      sa = list(range(n))
      rank = [ord(c) for c in s]
      k = 1
      tmp = [0] * n
      
      while True:
          # Sort by (rank[i], rank[i+k]) using counting sort
          max_rank = max(rank) + 1
          
          # Second key sort
          key2 = [rank[i + k] + 1 if i + k < n else 0 for i in range(n)]
          cnt = [0] * (max_rank + 1)
          for v in key2:
              cnt[v] += 1
          for i in range(1, len(cnt)):
              cnt[i] += cnt[i - 1]
          sa2 = [0] * n
          for i in range(n - 1, -1, -1):
              v = key2[i]
              cnt[v] -= 1
              sa2[cnt[v]] = i
          
          # First key sort
          key1 = [rank[i] for i in range(n)]
          cnt = [0] * max_rank
          for i in range(n):
              cnt[key1[sa2[i]]] += 1
          for i in range(1, max_rank):
              cnt[i] += cnt[i - 1]
          for i in range(n - 1, -1, -1):
              v = key1[sa2[i]]
              cnt[v] -= 1
              sa[cnt[v]] = sa2[i]
          
          # Reassign ranks
          tmp[sa[0]] = 0
          for idx in range(1, n):
              a = sa[idx - 1]
              b = sa[idx]
              ra = rank[a]
              rb = rank[b]
              if ra != rb:
                  tmp[b] = tmp[a] + 1
              else:
                  ra2 = rank[a + k] if a + k < n else -1
                  rb2 = rank[b + k] if b + k < n else -1
                  tmp[b] = tmp[a] + (1 if ra2 != rb2 else 0)
          rank, tmp = tmp, rank
          if rank[sa[-1]] == n - 1:
              break
          k <<= 1
  
      # Kasai LCP
      lcp = [0] * n
      p = [0] * n
      for i in range(n):
          p[sa[i]] = i
      h = 0
      for i in range(n):
          r = p[i]
          if r > 0:
              j = sa[r - 1]
              while i + h < n and j + h < n and s[i + h] == s[j + h]:
                  h += 1
              lcp[r] = h
              if h:
                  h -= 1
          else:
              h = 0
  
      best_len = 0
      best_pos = 0
      for r in range(1, n):
          l = lcp[r]
          if l > best_len:
              best_len = l
              best_pos = sa[r - 1] if sa[r - 1] < sa[r] else sa[r]
          elif l == best_len and l > 0:
              pos = sa[r - 1] if sa[r - 1] < sa[r] else sa[r]
              if pos < best_pos:
                  best_pos = pos
      return s[best_pos:best_pos + best_len] if best_len > 0 else ""

• #2Anthropic Claude Opus 5.5не розв'язано · 14 з 15 тестіввідповідь за 15 с · виконання 1.8 с · $0.03

  ✓	longest_repeat('banana')очікувалося 'ana'	<1 мс
  ✓	longest_repeat('abcd')очікувалося ''	<1 мс
  ✓	longest_repeat('aaaa')очікувалося 'aaa'	<1 мс

  ✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 951 мс⏱ 117 мс⏱ перевищено ліміт часу
  Код

  import random
  
  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
      M = (1 << 61) - 1
      B = random.randrange(10**6, 10**9)
      H = [0] * (n + 1)
      P = [1] * (n + 1)
      h = 0
      p = 1
      for i, c in enumerate(s):
          h = (h * B + ord(c)) % M
          H[i + 1] = h
          p = p * B % M
          P[i + 1] = p
  
      def hashes(L):
          pl = P[L]
          return [(H[i + L] - H[i] * pl) % M for i in range(n - L + 1)]
  
      def ok(L):
          hs = hashes(L)
          return len(set(hs)) < len(hs)
  
      lo, hi = 0, n - 1
      while lo < hi:
          mid = (lo + hi + 1) // 2
          if ok(mid):
              lo = mid
          else:
              hi = mid - 1
      L = lo
      if L == 0:
          return ""
      hs = hashes(L)
      seen = {}
      best = n
      for i, x in enumerate(hs):
          j = seen.get(x)
          if j is None:
              seen[x] = i
          elif j < best:
              best = j
      return s[best:best + L]

  Друга спроба

  не розв'язано · 14 з 15 тестіввідповідь за 19 с · $0.04

  Модель бачила кількість невдалих тестів, приклади з очікуваними та отриманими значеннями, а для прихованих тестів — лише причину помилки без вхідних даних. Не враховується в рейтингу та місцях.

  ✓	longest_repeat('banana')очікувалося 'ana'	3 мс
  ✓	longest_repeat('abcd')очікувалося ''	2 мс
  ✓	longest_repeat('aaaa')очікувалося 'aaa'	3 мс

  ✓ 2 мс✓ 2 мс✓ 2 мс✓ <1 мс✓ 3 мс✓ <1 мс✓ <1 мс✓ 1 мс✓ <1 мс⏱ 543 мс⏱ перевищено ліміт часу⏱ 445 мс

  Код

  import random
  
  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
      M = (1 << 61) - 1
      B = random.randrange(10**6, 10**9)
      H = [0] * (n + 1)
      P = [1] * (n + 1)
      h = 0
      p = 1
      i = 1
      for c in s.encode():
          h = (h * B + c) % M
          H[i] = h
          p = p * B % M
          P[i] = p
          i += 1
  
      def hashes(L):
          pl = P[L]
          return [(a - b * pl) % M for a, b in zip(H[L:], H)]
  
      def ok(L):
          if L <= 0:
              return True
          if L >= n:
              return False
          hs = hashes(L)
          return len(set(hs)) < len(hs)
  
      # galloping search
      lo = 0
      step = 1
      hi = None
      while True:
          cand = lo + step
          if cand >= n:
              hi = n - 1
              break
          if ok(cand):
              lo = cand
              step *= 2
          else:
              hi = cand - 1
              break
      while lo < hi:
          mid = (lo + hi + 1) // 2
          if ok(mid):
              lo = mid
          else:
              hi = mid - 1
      L = lo
      if L == 0:
          return ""
      hs = hashes(L)
      seen = {}
      best = n
      for i, x in enumerate(hs):
          j = seen.get(x)
          if j is None:
              seen[x] = i
          elif j < best:
              best = j
      return s[best:best + L]

• #4SpaceXAI Grok Build 0.1не розв'язано · 12 з 15 тестіввідповідь за 62 с · виконання 2.4 с · $0.02

  ✓	longest_repeat('banana')очікувалося 'ana'	<1 мс
  ✓	longest_repeat('abcd')очікувалося ''	2 мс
  ✓	longest_repeat('aaaa')очікувалося 'aaa'	<1 мс

  ✓ 3 мс✓ 1 мс✓ 1 мс✓ <1 мс✓ <1 мс✓ 1 мс✓ 1 мс✓ <1 мс✓ 1 мс⏱ перевищено ліміт часу⏱ перевищено ліміт часу⏱ перевищено ліміт часу
  Код

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n <= 1:
          return ""
      sa = list(range(n))
      rank = [ord(c) for c in s]
      tmp = [0] * n
      k = 1
      while k < n:
          sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))
          tmp[sa[0]] = 0
          for i in range(1, n):
              prev = sa[i - 1]
              curr = sa[i]
              prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
              curr_key = (rank[curr], rank[curr + k] if curr + k < n else -1)
              tmp[curr] = tmp[prev] + (1 if prev_key < curr_key else 0)
          rank = tmp[:]
          k <<= 1
      rnk = [0] * n
      for i in range(n):
          rnk[sa[i]] = i
      lcp = [0] * n
      h = 0
      for i in range(n):
          if rnk[i] == n - 1:
              h = 0
              continue
          j = sa[rnk[i] + 1]
          while i + h < n and j + h < n and s[i + h] == s[j + h]:
              h += 1
          lcp[rnk[i]] = h
          if h > 0:
              h -= 1
      max_l = max(lcp) if lcp else 0
      if max_l == 0:
          return ""
      min_start = n
      for i in range(n - 1):
          if lcp[i] == max_l:
              start1 = sa[i]
              start2 = sa[i + 1]
              min_start = min(min_start, start1, start2)
      return s[min_start:min_start + max_l]

  Друга спроба

  не розв'язано · 13 з 15 тестіввідповідь за 40 с · $0.02

  Модель бачила кількість невдалих тестів, приклади з очікуваними та отриманими значеннями, а для прихованих тестів — лише причину помилки без вхідних даних. Не враховується в рейтингу та місцях.

  ✓	longest_repeat('banana')очікувалося 'ana'	<1 мс
  ✓	longest_repeat('abcd')очікувалося ''	<1 мс
  ✓	longest_repeat('aaaa')очікувалося 'aaa'	2 мс

  ✓ <1 мс✓ <1 мс✓ <1 мс✓ 1 мс✓ 1 мс✓ 2 мс✓ 3 мс✓ <1 мс✓ <1 мс⏱ перевищено ліміт часу⏱ 100 мс⏱ перевищено ліміт часу

  Код

  from collections import defaultdict
  
  def longest_repeat(s: str) -> str:
      n = len(s)
      if n <= 1:
          return ""
      MOD1 = 10**9 + 7
      MOD2 = 10**9 + 9
      BASE1 = 131
      BASE2 = 137
      pow1 = [1] * (n + 1)
      pow2 = [1] * (n + 1)
      pre1 = [0] * (n + 1)
      pre2 = [0] * (n + 1)
      for i in range(n):
          pow1[i + 1] = pow1[i] * BASE1 % MOD1
          pow2[i + 1] = pow2[i] * BASE2 % MOD2
          pre1[i + 1] = (pre1[i] * BASE1 + ord(s[i])) % MOD1
          pre2[i + 1] = (pre2[i] * BASE2 + ord(s[i])) % MOD2
      def get_h1(l, r):
          val = (pre1[r] - pre1[l] * pow1[r - l] % MOD1 + MOD1) % MOD1
          return val
      def get_h2(l, r):
          val = (pre2[r] - pre2[l] * pow2[r - l] % MOD2 + MOD2) % MOD2
          return val
      max_L = 0
      low = 1
      high = n - 1
      while low <= high:
          mid = (low + high) // 2
          seen = set()
          has = False
          for i in range(n - mid + 1):
              h1 = get_h1(i, i + mid)
              h2 = get_h2(i, i + mid)
              key = (h1, h2)
              if key in seen:
                  has = True
                  break
              seen.add(key)
          if has:
              max_L = mid
              low = mid + 1
          else:
              high = mid - 1
      if max_L == 0:
          return ""
      pos = defaultdict(list)
      for i in range(n - max_L + 1):
          h1 = get_h1(i, i + max_L)
          h2 = get_h2(i, i + max_L)
          key = (h1, h2)
          pos[key].append(i)
      min_start = n
      for lst in pos.values():
          if len(lst) >= 2:
              min_start = min(min_start, lst[0])
      return s[min_start:min_start + max_L]

Вартість токенів: $0.11 · Як проходять раунди та нараховується рейтинг →