String Indexing TODO
Concept
A suffix array is an index that sorts all suffixes of a string lexicographically and stores just their starting positions in an array. Because it's sorted, an arbitrary pattern search can be done by binary search, and pairing it with an LCP array — the longest common prefix length between adjacent suffixes — lets you answer queries like repeated substrings or the count of distinct substrings in near-linear time. A suffix automaton (DAWG) encodes the same information as a state machine: it's the minimal deterministic automaton that recognizes every substring of the string, and its state count stays linear in the input length. An automaton can be built online, one character at a time, which makes it well suited to streaming, while a suffix array's compact memory footprint favors large static text. What both share at their core is turning "scan for the pattern every time" into "preprocess the text once and answer queries in constant or logarithmic time."
When the text is fixed — logs, traces — but search happens over and over, a grep-style linear scan turns straight into a cost the moment the data grows.
Code & Formula
# Day 9: 문자열 인덱스 — 서픽스 배열로 부분 문자열 검색을 이분 탐색으로 처리
# 모든 접미사를 정렬해 배열로 두면, 패턴 검색이 선형 스캔 대신 O(log n · m)에 끝난다.
def build_suffix_array(text):
return sorted(range(len(text)), key=lambda i: text[i:])
def search(text, sa, pattern):
lo, hi = 0, len(sa)
while lo < hi:
mid = (lo + hi) // 2
if text[sa[mid]:sa[mid] + len(pattern)] < pattern:
lo = mid + 1
else:
hi = mid
if lo == len(sa) or text[sa[lo]:sa[lo] + len(pattern)] != pattern:
return []
hits, i = [sa[lo]], lo + 1
while i < len(sa) and text[sa[i]:sa[i] + len(pattern)] == pattern:
hits.append(sa[i]); i += 1
return sorted(hits)
text = "the quick brown fox jumps over the lazy dog the fox runs"
sa = build_suffix_array(text)
print("서픽스 배열(앞 10개 시작 위치) =", sa[:10])
for pattern in ["fox", "the", "cat"]:
print(f"search('{pattern}') -> 위치 {search(text, sa, pattern)}")
docs/code/algorithms/algorithms-9.py
Exercise
Build a suffix array plus LCP array for a 10MB log file, then run the same 1,000 substring queries via plain linear scan versus binary search over the suffix array, and compare the timings.
Practical Connection
When you're repeatedly searching node logs or transaction traces for a specific address, function selector, or event signature, building the index once is operationally far more stable than doing a full scan every time.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.