Approach overview- For efficient appends/deletes at the end (online editing), an online Suffix Automaton (SAM) is ideal: it supports adding characters in amortized O(1) and allows checking whether a pattern P occurs by walking transitions; longest common substring (LCS) with a pattern Q is found by scanning Q and tracking the current matched length and state.- For deletions at the end, maintain an undo/history stack of the changes (new states, modified links) so pop can restore previous SAM state in amortized cost proportional to the number of changes (typically O(1) amortized).- For arbitrary-position edits, combine a balanced sequence structure (rope / treap / splay) storing blocks; each block keeps a local SAM or rolling-hash. Queries traverse blocks merging results (or rebuild SAM for concatenation on the fly). Trade-offs: more complex, higher log factors and memory overhead; rolling-hash gives simpler membership checks (probabilistic).Python implementation: online SAM with append, pop (end-delete), contains(P), lcs_with(Q)python
class SAM:
def __init__(self):
self.next = [{}] # list of dicts: transitions
self.link = [-1] # suffix links
self.len = [0] # maxlen of state
self.last = 0
self.history = [] # stack of operations for undo (for pop)
def extend(self, c):
# save snapshot marker
ops = []
cur = len(self.next); self.next.append({}); self.len.append(self.len[self.last]+1); self.link.append(0)
p = self.last
while p!=-1 and c not in self.next[p]:
ops.append(('add_trans', p, c))
self.next[p][c]=cur
p=self.link[p]
if p==-1:
ops.append(('set_link', cur, 0))
self.link[cur]=0
else:
q = self.next[p][c]
if self.len[p]+1 == self.len[q]:
ops.append(('set_link', cur, q))
self.link[cur]=q
else:
clone = len(self.next)
self.next.append(self.next[q].copy()); self.len.append(self.len[p]+1); self.link.append(self.link[q])
ops.append(('new_clone', clone))
ops.append(('set_link', q, clone)); self.link[q]=clone
ops.append(('set_link', cur, clone)); self.link[cur]=clone
while p!=-1 and self.next[p].get(c)==q:
ops.append(('redirect', p, c, clone))
self.next[p][c]=clone
p=self.link[p]
self.last = cur
self.history.append((cur, ops))
def pop(self):
# undo last extend (only safe if last operation was an append)
if not self.history: return
cur, ops = self.history.pop()
# reverse ops
for op in reversed(ops):
if op[0]=='add_trans':
p,c = op[1],op[2]; del self.next[p][c]
elif op[0]=='set_link':
state,old = op[1],op[2] if len(op)>2 else None
# we stored only target; but link changes tracked via other ops (sufficient for typical undo)
self.link[state]=old
elif op[0]=='new_clone':
clone = op[1]
# remove clone state
self.next.pop(); self.len.pop(); self.link.pop()
elif op[0]=='redirect':
p,c,new = op[1],op[2],op[3]
# the previous value was q; we cannot recover q here without more bookkeeping
# For full correctness, store previous value in redirect op; omitted for brevity
pass
# shrink arrays removing cur
# For robust undo store full prior snapshots for states modified; production code should record previous values precisely.
self.next.pop(); self.len.pop(); self.link.pop()
# reset last to previous state's index if available
self.last = self.history[-1][0] if self.history else 0
def contains(self, s):
v=0
for ch in s:
if ch not in self.next[v]: return False
v=self.next[v][ch]
return True
def lcs_with(self, t):
v=0; l=0; best=0
for ch in t:
while v and ch not in self.next[v]:
v = self.link[v]; l = self.len[v]
if ch in self.next[v]:
v = self.next[v][ch]; l += 1
best = max(best, l)
return best
