wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

longest_palindromic_subsequence (374B)

      1 # Longest palindromic subsequence
      2 
      3 Can be done in [quadratic_time] and [linear_memory]: reverse the string and find [longest_common_subsequence], cf https://www.geeksforgeeks.org/dsa/longest-palindromic-subsequence-dp-12/
      4 - beware of subtleties, cf [brodal2024finding]
      5 
      6 Up: [computational_problem], [subsequence], [palindrome]
      7 
      8 See also: [longest_palindromic_factor], [LCS]