任务 · 字符串 困难 Python ·

Longest repeated substring

def longest_repeat(s: str) -> str:

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

• 第 1 名SpaceXAI Grok Build 0.1未解决 · 通过 13/15 个测试生成耗时 78 秒 · 执行耗时 2.0 秒 · $0.02

  ✓	longest_repeat('banana')预期 'ana'	1 毫秒
  ✓	longest_repeat('abcd')预期 ''	<1 毫秒
  ✓	longest_repeat('aaaa')预期 'aaa'	<1 毫秒

  ✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 2 毫秒✓ 1 毫秒✓ 2 毫秒✓ 1 毫秒✓ 1 毫秒✓ <1 毫秒⏱ 超出时间限制⏱ 101 毫秒⏱ 超出时间限制
  代码

  def longest_repeat(s: str) -> str:
      if not s:
          return ""
      n = len(s)
      MOD1 = 10**9 + 7
      MOD2 = 10**9 + 9
      BASE1 = 131
      BASE2 = 137
      h1 = [0] * (n + 1)
      h2 = [0] * (n + 1)
      p1 = [1] * (n + 1)
      p2 = [1] * (n + 1)
      for i in range(n):
          h1[i + 1] = (h1[i] * BASE1 + ord(s[i])) % MOD1
          h2[i + 1] = (h2[i] * BASE2 + ord(s[i])) % MOD2
          p1[i + 1] = p1[i] * BASE1 % MOD1
          p2[i + 1] = p2[i] * BASE2 % MOD2
      def get_h(l, r):
          length = r - l
          val1 = (h1[r] - h1[l] * p1[length] % MOD1 + MOD1) % MOD1
          val2 = (h2[r] - h2[l] * p2[length] % MOD2 + MOD2) % MOD2
          return (val1, val2)
      def has_repeat(L):
          if L == 0:
              return True
          if L > n:
              return False
          seen = set()
          for i in range(n - L + 1):
              h = get_h(i, i + L)
              if h in seen:
                  return True
              seen.add(h)
          return False
      low = 0
      high = n
      while low < high:
          mid = (low + high + 1) // 2
          if has_repeat(mid):
              low = mid
          else:
              high = mid - 1
      maxL = low
      if maxL == 0:
          return ""
      pos = {}
      for i in range(n - maxL + 1):
          h = get_h(i, i + maxL)
          if h not in pos:
              pos[h] = []
          pos[h].append(i)
      min_first = n + 1
      best = ""
      for h, lst in pos.items():
          if len(lst) >= 2:
              first = lst[0]
              if first < min_first:
                  min_first = first
                  best = s[first: first + maxL]
      return best

  二次尝试

  未解决 · 通过 12/15 个测试生成耗时 50 秒 · $0.02

  模型可以看到失败的测试数量、包含预期值和返回值的失败示例，以及隐藏测试未通过的原因（不含输入数据）。此成绩不计入排名或评分。

  ✓	longest_repeat('banana')预期 'ana'	<1 毫秒
  ✓	longest_repeat('abcd')预期 ''	<1 毫秒
  ✓	longest_repeat('aaaa')预期 'aaa'	<1 毫秒

  ✓ <1 毫秒✓ <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))
      sa.sort(key=lambda i: s[i])
      rank = [0] * n
      rank[sa[0]] = 0
      for i in range(1, n):
          if s[sa[i]] != s[sa[i-1]]:
              rank[sa[i]] = rank[sa[i-1]] + 1
          else:
              rank[sa[i]] = rank[sa[i-1]]
      k = 1
      while k < n:
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
          new_rank = [0] * n
          new_rank[sa[0]] = 0
          for i in range(1, n):
              p = sa[i-1]
              c = sa[i]
              if (rank[p], rank[p + k] if p + k < n else -1) != (rank[c], rank[c + k] if c + k < n else -1):
                  new_rank[c] = new_rank[p] + 1
              else:
                  new_rank[c] = new_rank[p]
          rank = new_rank
          k <<= 1
      rank_pos = [0] * n
      for i in range(n):
          rank_pos[sa[i]] = i
      lcp = [0] * n
      h = 0
      for i in range(n):
          if rank_pos[i] == 0:
              h = 0
              continue
          j = sa[rank_pos[i] - 1]
          if h > 0:
              h -= 1
          while i + h < n and j + h < n and s[i + h] == s[j + h]:
              h += 1
          lcp[rank_pos[i]] = h
      max_l = 0
      for val in lcp:
          if val > max_l:
              max_l = val
      if max_l == 0:
          return ""
      min_start = n
      for i in range(1, n):
          if lcp[i] >= max_l:
              min_start = min(min_start, sa[i-1], sa[i])
      return s[min_start:min_start + max_l]

• 第 2 名OpenAI GPT-5.3-Codex未解决 · 通过 12/15 个测试生成耗时 7.9 秒 · 执行耗时 1.8 秒 · $0.0095

  ✓	longest_repeat('banana')预期 'ana'	<1 毫秒
  ✓	longest_repeat('abcd')预期 ''	<1 毫秒
  ✓	longest_repeat('aaaa')预期 'aaa'	<1 毫秒

  ✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒⏱ 答案错误⏱ 超出时间限制⏱ 答案错误
  代码

  from typing import List
  
  def longest_repeat(s: str) -> str:
      n = len(s)
      if n <= 1:
          return ""
  
      # Suffix array (prefix-doubling, O(n log n))
      sa = list(range(n))
      rank = [ord(c) - 97 for c in s]
      tmp = [0] * n
      k = 1
      while k < n:
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
  
          r = 0
          tmp[sa[0]] = 0
          for i in range(1, n):
              a, b = sa[i - 1], sa[i]
              pa = (rank[a], rank[a + k] if a + k < n else -1)
              pb = (rank[b], rank[b + k] if b + k < n else -1)
              if pa != pb:
                  r += 1
              tmp[b] = r
  
          rank, tmp = tmp, rank
          if r == n - 1:
              break
          k <<= 1
  
      # Kasai LCP array, O(n)
      inv = [0] * n
      for i, p in enumerate(sa):
          inv[p] = i
  
      lcp = [0] * (n - 1)
      h = 0
      for i in range(n):
          pos = inv[i]
          if pos == n - 1:
              h = 0
              continue
          j = sa[pos + 1]
          while i + h < n and j + h < n and s[i + h] == s[j + h]:
              h += 1
          lcp[pos] = h
          if h:
              h -= 1
  
      best_len = 0
      best_start = 0
  
      i = 0
      m = n - 1
      while i < m:
          if lcp[i] == 0:
              i += 1
              continue
          if lcp[i] < best_len:
              i += 1
              continue
  
          cur_max = lcp[i]
          min_pos = min(sa[i], sa[i + 1])
  
          j = i
          while j + 1 < m and lcp[j + 1] > 0:
              j += 1
              if lcp[j] > cur_max:
                  cur_max = lcp[j]
              p = sa[j + 1]
              if p < min_pos:
                  min_pos = p
  
          if cur_max > best_len:
              best_len = cur_max
              best_start = min_pos
          elif cur_max == best_len and cur_max > 0 and min_pos < best_start:
              best_start = min_pos
  
          i = j + 1
  
      if best_len == 0:
          return ""
      return s[best_start:best_start + best_len]

  二次尝试

  未解决 · 通过 14/15 个测试生成耗时 11 秒 · $0.01

  模型可以看到失败的测试数量、包含预期值和返回值的失败示例，以及隐藏测试未通过的原因（不含输入数据）。此成绩不计入排名或评分。

  ✓	longest_repeat('banana')预期 'ana'	1 毫秒
  ✓	longest_repeat('abcd')预期 ''	<1 毫秒
  ✓	longest_repeat('aaaa')预期 'aaa'	<1 毫秒

  ✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 1 毫秒✓ <1 毫秒✓ 1 毫秒✓ <1 毫秒⏱ 803 毫秒⏱ 超出时间限制⏱ 591 毫秒

  代码

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
  
      # Build suffix array with O(n log n) counting-sort doubling
      sa = list(range(n))
      rank = [ord(c) - 96 for c in s]  # 1..26
      tmp = [0] * n
      k = 1
      maxv = max(27, n) + 5
  
      while True:
          m = max(max(rank) + 2, n + 2, 30)
  
          # sort by second key rank[i+k]
          cnt = [0] * m
          sec = [0] * n
          for i in range(n):
              v = rank[i + k] if i + k < n else 0
              sec[i] = v
              cnt[v] += 1
          ssum = 0
          for i in range(m):
              c = cnt[i]
              cnt[i] = ssum
              ssum += c
          sa2 = [0] * n
          for idx in sa:
              v = sec[idx]
              sa2[cnt[v]] = idx
              cnt[v] += 1
  
          # sort by first key rank[i]
          cnt = [0] * m
          for i in range(n):
              cnt[rank[i]] += 1
          ssum = 0
          for i in range(m):
              c = cnt[i]
              cnt[i] = ssum
              ssum += c
          sa_new = [0] * n
          for idx in sa2:
              v = rank[idx]
              sa_new[cnt[v]] = idx
              cnt[v] += 1
          sa = sa_new
  
          # re-rank
          r = 1
          tmp[sa[0]] = r
          for i in range(1, n):
              a = sa[i - 1]
              b = sa[i]
              a1 = rank[a]
              b1 = rank[b]
              a2 = rank[a + k] if a + k < n else 0
              b2 = rank[b + k] if b + k < n else 0
              if a1 != b1 or a2 != b2:
                  r += 1
              tmp[b] = r
          rank, tmp = tmp, rank
          if r == n:
              break
          k <<= 1
  
      # Kasai LCP
      pos = [0] * n
      for i, p in enumerate(sa):
          pos[p] = i
      lcp = [0] * (n - 1)
      h = 0
      for i in range(n):
          pi = pos[i]
          if pi == n - 1:
              h = 0
              continue
          j = sa[pi + 1]
          while i + h < n and j + h < n and s[i + h] == s[j + h]:
              h += 1
          lcp[pi] = h
          if h:
              h -= 1
  
      best_len = 0
      best_start = 0
      for i, v in enumerate(lcp):
          if v > best_len:
              best_len = v
              a = sa[i]
              b = sa[i + 1]
              best_start = a if a < b else b
          elif v == best_len and v > 0:
              a = sa[i]
              b = sa[i + 1]
              st = a if a < b else b
              if st < best_start:
                  best_start = st
  
      return s[best_start:best_start + best_len] if best_len > 0 else ""

• 第 3 名DeepSeek V4 Pro 0423未解决 · 通过 12/15 个测试生成耗时 7.0 秒 · 执行耗时 2.4 秒 · $0.0011

  ✓	longest_repeat('banana')预期 'ana'	<1 毫秒
  ✓	longest_repeat('abcd')预期 ''	<1 毫秒
  ✓	longest_repeat('aaaa')预期 'aaa'	<1 毫秒

  ✓ <1 毫秒✓ 1 毫秒✓ 1 毫秒✓ 5 毫秒✓ 1 毫秒✓ 1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒⏱ 超出时间限制⏱ 超出时间限制⏱ 超出时间限制
  代码

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
      
      # Suffix array construction using doubling algorithm
      sa = list(range(n))
      rank = [ord(c) - 97 for c in s]
      tmp = [0] * n
      k = 1
      
      while k < n:
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + 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 curr_key != prev_key else 0)
          rank, tmp = tmp, rank
          k <<= 1
      
      # LCP array construction using Kasai's algorithm
      inv_sa = [0] * n
      for i, idx in enumerate(sa):
          inv_sa[idx] = i
      
      lcp = [0] * (n - 1)
      h = 0
      for i in range(n):
          if inv_sa[i] > 0:
              j = sa[inv_sa[i] - 1]
              while i + h < n and j + h < n and s[i + h] == s[j + h]:
                  h += 1
              lcp[inv_sa[i] - 1] = h
              if h > 0:
                  h -= 1
      
      # Find maximum LCP and earliest suffix position
      max_len = 0
      min_pos = n
      for i in range(n - 1):
          if lcp[i] > max_len:
              max_len = lcp[i]
              min_pos = min(sa[i], sa[i + 1])
          elif lcp[i] == max_len and max_len > 0:
              min_pos = min(min_pos, sa[i], sa[i + 1])
      
      if max_len == 0:
          return ""
      return s[min_pos:min_pos + max_len]

  二次尝试

  未解决 · 通过 14/15 个测试生成耗时 7.1 秒 · $0.0016

  模型可以看到失败的测试数量、包含预期值和返回值的失败示例，以及隐藏测试未通过的原因（不含输入数据）。此成绩不计入排名或评分。

  ✓	longest_repeat('banana')预期 'ana'	<1 毫秒
  ✓	longest_repeat('abcd')预期 ''	<1 毫秒
  ✓	longest_repeat('aaaa')预期 'aaa'	<1 毫秒

  ✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ <1 毫秒✓ 2 毫秒✓ 2 毫秒✓ 2 毫秒✓ <1 毫秒⏱ 656 毫秒⏱ 超出时间限制⏱ 498 毫秒

  代码

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
      
      # Suffix array construction using SA-IS algorithm for O(n) time
      # but here we implement a fast doubling with integer keys
      sa = list(range(n))
      rank = [ord(c) - 97 for c in s]
      tmp = [0] * n
      k = 1
      
      while k < n:
          # Use tuple sorting with a key lambda is still O(n log n), but more efficient in Python
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + 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 curr_key != prev_key else 0)
          rank, tmp = tmp, rank
          if rank[sa[-1]] == n - 1:
              break
          k <<= 1
      
      # LCP array using Kasai's algorithm
      inv_sa = [0] * n
      for i, idx in enumerate(sa):
          inv_sa[idx] = i
      
      max_len = 0
      min_pos = n
      h = 0
      for i in range(n):
          if inv_sa[i] > 0:
              j = sa[inv_sa[i] - 1]
              while i + h < n and j + h < n and s[i + h] == s[j + h]:
                  h += 1
              if h > max_len:
                  max_len = h
                  min_pos = min(i, j)
              elif h == max_len and h > 0:
                  min_pos = min(min_pos, i, j)
              if h > 0:
                  h -= 1
      
      if max_len == 0:
          return ""
      return s[min_pos:min_pos + max_len]

• 第 4 名MoonshotAI Kimi K2.7 Code未解决 · 通过 0/15 个测试生成耗时 120 秒

  回复中无代码

  ✗	longest_repeat('banana')预期 'ana'回复中无代码	—
  ✗	longest_repeat('abcd')预期 ''回复中无代码	—
  ✗	longest_repeat('aaaa')预期 'aaa'回复中无代码	—

  ✗ 回复中无代码✗ 回复中无代码✗ 回复中无代码✗ 回复中无代码✗ 回复中无代码✗ 回复中无代码✗ 回复中无代码✗ 回复中无代码✗ 回复中无代码⏱ 回复中无代码⏱ 回复中无代码⏱ 回复中无代码

Token 成本: $0.06 · 轮次运行与评分规则 →