约束最长公共子序列和子字符串问题的算法

1The 5th National Big Data Health Science ConferenceUniversity of South Carolina Columbia, SCFeb. 2 -3, 2024An Algorithm for the Constrained Longest Common Subsequence and Substring Problem Rao LiUniversity of South Carolina AikenJoint work with JyotishmoyDeka, Kaushik Deka, and Dorothy Li2Subsequences and Substrings-Let ∑ be an alphabet and Sa string over ∑. A subsequence of a string Sis obtained by deleting zero or more letters from S.If S = “ACGTU”, then “ATU” is a subsequence of S.-A substring of a string Sis a subsequence of S consists of consecutive letters in S.If S = “ACGTU”, then “CGT” is a substring of S,“ATU” is not a substring of S, -Every substring of Sis also a subsequence of S. -The empty string is a subsequence and a substring of any string. 3The Longest Common Subsequence Problem for Two Strings-The longest common subsequence problem for two strings X and Y is to find a longest string, denoted LCSSeq(X, Y), which is a subsequence of both X and Y. -Obviously, the set o