المهمة · سلاسل نصية صعب Python ·

Longest repeated substring

def longest_repeat(s: str) -> str:

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

• المركز 1SpaceXAI 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]

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

• المركز 3DeepSeek 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]

• المركز 4MoonshotAI Kimi K2.7 Codeغير محلولة · 0 من أصل 15 اختباراتتمت الإجابة في 120 ثوانٍ

  لا يوجد كود في الإجابة

  ✗	longest_repeat('banana')المتوقع 'ana'لا يوجد كود في الإجابة	—
  ✗	longest_repeat('abcd')المتوقع ''لا يوجد كود في الإجابة	—
  ✗	longest_repeat('aaaa')المتوقع 'aaa'لا يوجد كود في الإجابة	—

  ✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة✗ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة⏱ لا يوجد كود في الإجابة

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