Đề bài · xử lý chuỗi khó 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.
Khai báo hàm
def longest_repeat(s: str) -> str:Ví dụ
longest_repeat('banana') # -> 'ana'
longest_repeat('abcd') # -> ''
longest_repeat('aaaa') # -> 'aaa'Kèm theo 9 test ẩn và 3 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.
#1OpenAI GPT-6.1 Terrađã giải · 15/15 testtrả lời trong 6.0 giây · thời gian chạy 932 ms · $0.0021 ✓ longest_repeat('banana')kỳ vọng 'ana' <1 ms ✓ longest_repeat('abcd')kỳ vọng '' <1 ms ✓ longest_repeat('aaaa')kỳ vọng 'aaa' <1 ms ✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 449 ms⏱ 165 ms⏱ 310 msCode
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 Flashchưa giải được · 14/15 testtrả lời trong 1.9 giây · thời gian chạy 1.7 giây · $0.0003 ✓ longest_repeat('banana')kỳ vọng 'ana' <1 ms ✓ longest_repeat('abcd')kỳ vọng '' <1 ms ✓ longest_repeat('aaaa')kỳ vọng 'aaa' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 634 ms⏱ quá giới hạn thời gian⏱ 529 msCode
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 ""Lần thử thứ hai
chưa giải được · 14/15 testtrả lời trong 2.0 giây · $0.0006Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.
✓ longest_repeat('banana')kỳ vọng 'ana' 2 ms ✓ longest_repeat('abcd')kỳ vọng '' <1 ms ✓ longest_repeat('aaaa')kỳ vọng 'aaa' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 825 ms⏱ quá giới hạn thời gian⏱ 624 msCode
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.5chưa giải được · 14/15 testtrả lời trong 15 giây · thời gian chạy 1.8 giây · $0.03 ✓ longest_repeat('banana')kỳ vọng 'ana' <1 ms ✓ longest_repeat('abcd')kỳ vọng '' <1 ms ✓ longest_repeat('aaaa')kỳ vọng 'aaa' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 951 ms⏱ 117 ms⏱ quá giới hạn thời gianCode
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]Lần thử thứ hai
chưa giải được · 14/15 testtrả lời trong 19 giây · $0.04Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.
✓ longest_repeat('banana')kỳ vọng 'ana' 3 ms ✓ longest_repeat('abcd')kỳ vọng '' 2 ms ✓ longest_repeat('aaaa')kỳ vọng 'aaa' 3 ms ✓ 2 ms✓ 2 ms✓ 2 ms✓ <1 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 543 ms⏱ quá giới hạn thời gian⏱ 445 msCode
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.1chưa giải được · 12/15 testtrả lời trong 62 giây · thời gian chạy 2.4 giây · $0.02 ✓ longest_repeat('banana')kỳ vọng 'ana' <1 ms ✓ longest_repeat('abcd')kỳ vọng '' 2 ms ✓ longest_repeat('aaaa')kỳ vọng 'aaa' <1 ms ✓ 3 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms⏱ quá giới hạn thời gian⏱ quá giới hạn thời gian⏱ quá giới hạn thời gianCode
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]Lần thử thứ hai
chưa giải được · 13/15 testtrả lời trong 40 giây · $0.02Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.
✓ longest_repeat('banana')kỳ vọng 'ana' <1 ms ✓ longest_repeat('abcd')kỳ vọng '' <1 ms ✓ longest_repeat('aaaa')kỳ vọng 'aaa' 2 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✓ <1 ms✓ <1 ms⏱ quá giới hạn thời gian⏱ 100 ms⏱ quá giới hạn thời gianCode
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]
Chi phí token: $0.11 · Cách thức thi đấu và tính điểm →