[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhlongest_common_subsequence.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "longest common subsequence" source: https://www.jemoka.com/posts/kbhlongest_common_subsequence/ --- BDFH is a subsequence of ABCDEFGH. Given two lists, what’s the longest common subsequence? optimal substructure We consider sub problems’ of finding LCS of prefixes \(C[i,j]\). Casework: C[i,j] = … for A[i] = B[j], then C[i,j] = C[i-1, j-1] + 1 for A[i] != B[j] = max(C[i,j-1], C[i-1,j]) if i=0 or j=0, then 0 Filling this table is \(O\qty(nm)\), and backtracing takes \(O\qty(n+m)\).