Tugas · string sulit Python ·
Longest repeated substring
Return the longest substring that occurs in s at least twice; the occurrences may overlap. If several substrings have that length, return the one whose first occurrence starts earliest. Return "" if no character repeats. s has lowercase letters only and can be up to 100,000 characters long.
Tanda tangan
def longest_repeat(s: str) -> str:Contoh
longest_repeat('banana') # -> 'ana'
longest_repeat('abcd') # -> ''
longest_repeat('aaaa') # -> 'aaa'Ditambah 9 pengujian tersembunyi dan 3 pengujian input besar dengan batas waktu; inputnya tidak ditampilkan. Tugas diberikan kepada model dalam bahasa Inggris.
#1OpenAI GPT-6.1 Terraselesai · 15 dari 15 pengujianrespons dalam 6.0 dtk · waktu eksekusi 932 md · $0.0021 ✓ longest_repeat('banana')diharapkan 'ana' <1 md ✓ longest_repeat('abcd')diharapkan '' <1 md ✓ longest_repeat('aaaa')diharapkan 'aaa' <1 md ✓ <1 md✓ <1 md✓ 2 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 449 md⏱ 165 md⏱ 310 mdKode
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 Flashtidak selesai · 14 dari 15 pengujianrespons dalam 1.9 dtk · waktu eksekusi 1.7 dtk · $0.0003 ✓ longest_repeat('banana')diharapkan 'ana' <1 md ✓ longest_repeat('abcd')diharapkan '' <1 md ✓ longest_repeat('aaaa')diharapkan 'aaa' <1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ 2 md✓ 1 md✓ <1 md✓ <1 md✓ <1 md⏱ 634 md⏱ batas waktu terlampaui⏱ 529 mdKode
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 ""Percobaan kedua
tidak selesai · 14 dari 15 pengujianrespons dalam 2.0 dtk · $0.0006Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.
✓ longest_repeat('banana')diharapkan 'ana' 2 md ✓ longest_repeat('abcd')diharapkan '' <1 md ✓ longest_repeat('aaaa')diharapkan 'aaa' <1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 825 md⏱ batas waktu terlampaui⏱ 624 mdKode
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.5tidak selesai · 14 dari 15 pengujianrespons dalam 15 dtk · waktu eksekusi 1.8 dtk · $0.03 ✓ longest_repeat('banana')diharapkan 'ana' <1 md ✓ longest_repeat('abcd')diharapkan '' <1 md ✓ longest_repeat('aaaa')diharapkan 'aaa' <1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 951 md⏱ 117 md⏱ batas waktu terlampauiKode
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]Percobaan kedua
tidak selesai · 14 dari 15 pengujianrespons dalam 19 dtk · $0.04Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.
✓ longest_repeat('banana')diharapkan 'ana' 3 md ✓ longest_repeat('abcd')diharapkan '' 2 md ✓ longest_repeat('aaaa')diharapkan 'aaa' 3 md ✓ 2 md✓ 2 md✓ 2 md✓ <1 md✓ 3 md✓ <1 md✓ <1 md✓ 1 md✓ <1 md⏱ 543 md⏱ batas waktu terlampaui⏱ 445 mdKode
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.1tidak selesai · 12 dari 15 pengujianrespons dalam 62 dtk · waktu eksekusi 2.4 dtk · $0.02 ✓ longest_repeat('banana')diharapkan 'ana' <1 md ✓ longest_repeat('abcd')diharapkan '' 2 md ✓ longest_repeat('aaaa')diharapkan 'aaa' <1 md ✓ 3 md✓ 1 md✓ 1 md✓ <1 md✓ <1 md✓ 1 md✓ 1 md✓ <1 md✓ 1 md⏱ batas waktu terlampaui⏱ batas waktu terlampaui⏱ batas waktu terlampauiKode
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]Percobaan kedua
tidak selesai · 13 dari 15 pengujianrespons dalam 40 dtk · $0.02Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.
✓ longest_repeat('banana')diharapkan 'ana' <1 md ✓ longest_repeat('abcd')diharapkan '' <1 md ✓ longest_repeat('aaaa')diharapkan 'aaa' 2 md ✓ <1 md✓ <1 md✓ <1 md✓ 1 md✓ 1 md✓ 2 md✓ 3 md✓ <1 md✓ <1 md⏱ batas waktu terlampaui⏱ 100 md⏱ batas waktu terlampauiKode
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]
Biaya token: $0.11 · Cara babak dijalankan dan dinilai →