<prompt> Etsa algorithm bakeng sa ho fumana tatelano e telele ka ho fetisisa e tloaelehileng lipakeng tsa likhoele tse pelis1 ABCDGH s2 AEDFHR  <response>: Instruction in English: Design an algorithm for finding the longest common subsequence between two strings . Response in English: The longest common subsequence LCS problem is the problem of finding the longest subsequence common to two sequences. It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.A classic way of solving this problem is through the use of dynamic programming. Here is an algorithm that finds the length of the longest common subsequence between strings s1 and s2:1. Initialize a 2D array dp with dimensions lens11 X lens21. The first row and column of dp are filled with zeros to represent the base case where the length of one of the strings is zero.2. Start iterating through the characters of s1 and s2. Let i and j be the indices of the characters in s1 and s2, respectively.3. For each pair of characters, if s1i s2j, then the length of the common subsequence ending at index i in s1 and j in s2 is one more than the length of the common subsequence ending at the previous index in both strings. In other words, dpi1j1 dpij 1.4. However, if the characters are not equal, then the length of the LCS would be the maximum of the LCS ending at the previous index in s1 or the LCS ending at the previous index in s2. Thus, dpi1j1 maxdpij1, dpi1j.5. Return the value in the last cell of the dp table, i.e. dp-1-1.To find the actual longest common subsequence, we can backtrack through the dp table starting from the last cell:1. Initialize an empty string lcs.2. Start from the last cell dp-1-1 and move towards the first cell dp00.3. If the characters at the current cells indices in s1 and s2 are equal, then this character is part of the LCS. Add it to the lcs string and move diagonally to the top-left cell.4. Else, move to the cell with the larger value, either above the current cell or to its left.5 . Response in Sesotho: Bothata ba nako e telele ka ho fetisisa bo tloaelehileng LCS ke bothata ba ho fumana tatelano e telele ka ho fetisisa e tloaelehileng ho tse peli tse latellanang. E fapane le bothata bo bolelele ka ho fetesisa bo tloaelehileng: ho fapana le li-substrings, tse latelang ha li hlokehe ho nka maemo a latellanang ka hara tatelano ea mantlha. Mokhoa oa khale oa ho rarolla bothata bona ke ka ho sebelisa mananeo a matla. Mona ke algorithm e fumanang bolelele ba tatelano e telele ka ho fetisisa e tloaelehileng lipakeng tsa likhoele s1 le s2: 1. Qala sehlopha sa 2D dp ka litekanyo lens11 X lens21. Mola oa pele le kholomo ea dp li tlatsitsoe ka zero ho emela nyeoe ea motheo moo bolelele ba e ngoe ea likhoele e leng zero. 2. Qala ho pheta-pheta ka litlhaku tsa s1 le s2. E re i le j e be li-indices tsa litlhaku ho s1 le s2, ka ho latellana. 3. Bakeng sa para ka nngwe ya ditlhaku, haeba s1i s2j, bolelele ba tatelano e tlwaelehileng e qetellang ka index i ho s1 le j ho s2 ke e le nngwe ho feta bolelele ba. tatelano e tlwaelehileng e qetellang ho index e fetileng meleng e ka bobedi. Ka mantsoe a mang, dpi1j1 dpij 1. 4. Leha ho le joalo, haeba litlhaku li sa lekane, joale bolelele ba LCS e tla ba boholo ba LCS bo qetellang ho index e fetileng ho s1 kapa LCS e qetellang ho index e fetileng ho s2. Kahoo, dpi1j1 maxdpij1, dpi1j. 5. Khutlisetsa boleng seleng ea ho qetela ea tafole ea dp, ke hore dp-1-1. Ho fumana tatelano e telele ka ho fetesisa e tloaelehileng, re ka khutlela morao ka hara tafole ea dp ho qala ho sele ea ho qetela: 1. Qala khoele e se nang letho lcs. 2. Qala ho tloha sele ea ho qetela dp-1-1 me u lebe ho sele ea pele dp00. 3. Haeba litlhaku tsa li-indices tsa sele ea hona joale ho s1 le s2 li lekana, joale tlhaku ena ke karolo ea LCS. E kenye khoeleng ea lcs me u tsamaele ka nqa e ka holimo ho le letšehali. 4. Ho seng joalo, fallela seleng e nang le boleng bo boholoanyane, ebang ke ka holima sele ea hona joale kapa ka ho le letšehali. 5 