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.
Where it lands in Jayverse
- gitboard: build the suffix-array index once and expose it as a search panel. Index devnet/Sepolia trace logs once instead of re-grepping raw logs each time an incident needs a specific address, selector or event signature traced.
- Auditor: point investigations at the indexed search, not raw logs. Faster trace lookup during an incident is itself evidence the methodology was followed, not just a convenience.
- CI: let query time be the trigger to build the index. If ad hoc grep gets slow during a CI-triggered incident replay, that's the signal to build the suffix array rather than optimize the grep further.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| lexicographically | 사전순으로 · 접미사들을 알파벳 순서로 정렬한다는 뜻. "sorts all suffixes of a string lexicographically" |
| well suited to | ~에 잘 맞는, 적합한 · 온라인 빌드 방식이 스트리밍에 알맞다는 뜻. "which makes it well suited to streaming" |
| favor | ~에 유리하다, ~을 선호하게 만들다 · 어떤 구조가 특정 상황에 더 적합하다는 뜻. "favors large static text" |
| turn X into Y | X를 Y로 바꾸다 · 매번 스캔하던 것을 한 번 전처리로 바꾼다는 뜻. "preprocess the text once and answer queries" |
| operationally | 운영상으로, 실제 운용 측면에서 · 인덱스를 한 번 만드는 편이 안정적이라는 뜻. "operationally far more stable" |
| memory footprint | 메모리 점유량 · 자료구조가 차지하는 메모리 크기. "compact memory footprint favors large" |
| DAWG | 접미사 오토마톤(Deterministic Acyclic Word Graph) · 문자열의 모든 부분 문자열을 인식하는 최소 상태 기계. "A suffix automaton (DAWG) encodes the same information as a state machine" |
| LCP | 최장 공통 접두사(Longest Common Prefix) · 인접한 접미사 사이의 공통 접두사 길이를 저장하는 배열. "pairing it with an LCP array" |
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/.