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

1、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 Jyotishmoy Deka,Kaushik Deka,and Dorothy Li2Subsequences a

2、nd Substrings-Let be an alphabet and S a string over.A subsequence of a string S is obtained by deleting zero or more letters from S.If S=“ACGTU”,then“ATU”is a subsequence of S.-A substring of a string S is a subsequence of S consists of consecutive letters in S.If S=“ACGTU”,then“CGT”is a substring

3、of S,“ATU”is not a substring of S,-Every substring of S is 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,denot

4、ed LCSSeq(X,Y),which is a subsequence of both X and Y.-Obviously,the set of LCSSeq(X,Y)and the set LCSSeq(Y,X)are the same.|LCSSeq(X,Y)|=|LCSSeq(Y,X)|.4The Longest Common Substring Problem for Two Strings-The longest common substring problem for two strings X and Y is to find a longest string,denote

5、d LCSStr(X,Y),which is a substring of both X and Y.-Obviously,the set of LCSStr(X,Y)and the set LCSStr(Y,X)are the same.|LCSStr(X,Y)|=|LCSStr(Y,X)|.5TheLongest Common Subsequence and Substring Problem for Two Strings-In 1,Li,Deka,and Deka introduced the longest common subsequence and substring probl

6、em for two strings X and Y which is to find a longest string,denoted LCSSeqStr(X,Y),that is a subsequence of X and a substring Y.-1 R.Li,J.Deka,and K.Deka,An algorithm for the longest common subsequence and substring problem,Journal of Math and Informatics 25(2023)77-81.6TheLongest Common Subsequenc