Given two strings S of length n and T of length m, we want to reconstruct T from S with a minimum number of the following operations: i) delete a character from S, ii) insert a character into S, or iii) swap two consecutive characters in S. For example, when S = yorkun and T = ayokru, one can insert an 'a' at index 1 of S, swap 'r' and 'k' in S, and remove 'n' from the end of S. Therefore, we can reconstruct T from S with 3 operations. Devise a DP solution to report the minimum number of operations to reconfigure S to T. The actual operations in a minimum-cost reconfiguration are not needed. It suffices to show Steps 1 and 2 in the DP paradigm in your solution. In Step 1, you must specify the subproblems, and how the value of the optimal solutions for smaller subproblems can be used to describe those of large subproblems. In Step 2, you must write down a recursive formula for the minimum number of operations to reconfigure. Assume indices start at 1.

Given two strings S of length n and T of length m, we want to reconstruct T from S with a minimum number of the following operations: i) delete a character from S, ii) insert a character into S, or iii) swap two consecutive characters in S. For example, when S = yorkun and T = ayokru, one can insert an 'a' at index 1 of S, swap 'r' and 'k' in S, and remove 'n' from the end of S. Therefore, we can reconstruct T from S with 3 operations. Devise a DP solution to report the minimum number of operations to reconfigure S to T. The actual operations in a minimum-cost reconfiguration are not needed. It suffices to show Steps 1 and 2 in the DP paradigm in your solution. In Step 1, you must specify the subproblems, and how the value of the optimal solutions for smaller subproblems can be used to describe those of large subproblems. In Step 2, you must write down a recursive formula for the minimum number of operations to reconfigure. Assume indices start at 1.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter8: Arrays And Strings

Section: Chapter Questions

Problem 24PE

See similar textbooks

Similar questions

You are given a string X of length n and another string Y of length m ≤n. Say,the indexes p1, p2, p3, p4 and q1, q2, q3, q4 form two sub-sequences, i.e., 0 ≤ p1 < p2 < p3 < p4 < nand 0 ≤q1 < q2 < q3 < q4 < n; then, they are non-overlapping if p4 < q1.The task is to count the maximum number of non-overlapping sub-sequences of X that are thesame as Y . Thus, if X = GAXTYAWBGTAUGBTABGRGTAXB and Y = GTAB, then the answer is3 as shown by the red fonts. We cannot select the underlined GTAB as it overlaps with a red GTAB(i.e., among overlapping sub-sequences, you can select only one of them).Describe an O(m + n) time algorithm to obtain the count. Write a pseudo-code.
The reverse of a string x denoted by rev(x) and is defined by the following recursiverule: •rev(ε) = ε•rev(xa) = a.rev(x) Prove that if A is a regular set then so is the following set:rev(A) = {rev(x) : x ∈A}
Given a string S, find the longest palindromic substring in S. Substring of string S: S[ i . . . . j ] where 0 ≤ i ≤ j < len(S). Palindrome string: A string which reads the same backwards. More formally, S is palindrome if reverse(S) = S. Incase of conflict, return the substring which occurs first ( with the least starting index). Example 1: Input: S = "aaaabbaa" Output: aabbaa Explanation: The longest Palindromic substring is "aabbaa".
Let A be the set of all strings of decimal digits of length 5. For example 24157 and05189 are strings in A.(a) How many strings in A have exactly one 7?(b) How many strings in A have at least two 2’s?(c) How many strings in A have the digits in a strictly decreasing order? For example97643 and 54321 are such strings, but 14820 and 95421 are not.
Computer Science you are given a string X of length n and another string Y of length m ≤n. Say,the indexes p1, p2, p3, p4 and q1, q2, q3, q4 form two sub-sequences, i.e., 0 ≤ p1 < p2 < p3 < p4 < nand 0 ≤q1 < q2 < q3 < q4 < n; then, they are non-overlapping if p4 < q1.The task is to count the maximum number of non-overlapping sub-sequences of X that are thesame as Y . Thus, if X = GAXTYAWBGTAUGBTABGRGTAXB and Y = GTAB, then the answer is3 as shown by the red fonts. We cannot select the underlined GTAB as it overlaps with a red GTAB(i.e., among overlapping sub-sequences, you can select only one of them).Describe an O(m + n) time algorithm to obtain the count. Write a pseudo-code.
2. Let n be a positive integer, and let A be a list of positive integers. We say that the integer n can be factorized by A if there exists a sequence of integers 11, 12,..., ik (with 0 ≤i; < len (A), for j = 1,..., k) such that n is the product of the integers A[i], A[i2],..., A[ik]. Write an efficient algorithm factorizable (n, A) that returns True if n can be factorized by A, and False otherwise. Prove that your algorithm is correct, and bound its running time. Larger scores will be awarded to faster solutions. Example 1: if n = 6 and A [4,2,3], then factorizable (n, A) should return True, L[1] * L[2]. since n == Example 2: if n = 8 and A = L[0] * L[0] * L[0]. [2,5], then factorizable (n, A) should return True, since ,2,3,5,7], then factorizable (n, A) should return Example 3: if n = 13 and A = False since n cannot be factorized by A.
A string S consisting of uppercase English letters is given. In one move we can delete seven letters from S, forming the word "BALLOON" (one 'B' one A, two 'L's, two 'O's and one 'N'), and leave a shorter word in S. If the remaining letters in the shortened S are sufficient to allow another instance of the word "BALLOON" to be removed, next move can be done. What is the maximum number of such moves that we can apply using python
Given the following sets: U= {1,2,3,4,5,6,7,8,}, A={1,4,5,7}, B= {2,5,6,7,}, and C= {3,4,6,7} Complete the following set operations: a. A U(BUC) b. (A N (B N C))' . c. (A N B) U ( A N C) d. (A N B')U (A N C')
Correct answer will be upvoted else downvoted. Computer science. We should characterize the expense of a string s as the number of file sets I and j (1≤i<j<|s|) with the end goal that si=sj and si+1=sj+1. You are given two positive integers n and k. Among all strings with length n that contain just the principal k characters of the Latin letters in order, find a string with least conceivable expense. In case there are different such strings with least expense — see as any of them. Input The main line contains two integers n and k (1≤n≤2⋅105;1≤k≤26). Output Print the string s to such an extent that it comprises of n characters, every its character is one of the k first Latin letters, and it has the base conceivable expense among this load of strings. In case there are various such strings — print any of them
Modulo arithmeticFor two integers ‘a’ and ‘b’ and a positive integer ‘n’, let + represent the operation a + b = (a+b)mod(n), that is, the result of a + b is the remainder of the usual sum a + b after dividing by n (using a natural representation). Similarly, let * represent the operation a * b = (a*b)mod(n), that is, the result of a * b is the remainder of the product a*b after dividing by n. For example using the set S = {2, 5, 8} and n = 9, 5 + 8 = 4, since 4 is the remainder after dividing 13 (5 + 8) by 9; and 2 * 8 = 7, since 7 is the remainder after dividing 16 (2*8) by 9.a. For each set S and number n specified below, create two “operation” tables (these are called Cayley tables), one showing the results for the operation +, and one showing the results of the operation * for each pair of elements from S (see the example tables in the notes).i. S1 = {0, 1} and n = 2ii. S2 = {1, 2} and n = 3iii. S3 = {0, 2, 4, 6} and n = 8iv. S4 = {1, 3, 5, 7} and n = 8v. S5 = {1, 2, 3, 4} and n =…
The median m of a sequence of n elements is the element that would fall in the middle if the sequence was sorted. That is, e ≤ m for half the elements, and m ≤ e for the others. Clearly, one can obtain the median by sorting the sequence, but one can do quite a bit better with the following algorithm that finds the kth element of a sequence between a (inclusive) and b (exclusive). (For the median, use k = n/2, a = 0, and b = n.) select(k, a, b)Pick a pivot p in the subsequence between a and b.Partition the subsequence elements into three subsequences: the elements <p, =p, >p Let n1, n2, n3 be the sizes of each of these subsequences.if k < n1 return select(k, 0, n1).else if (k > n1 + n2) return select(k, n1 + n2, n).else return p. c++
A substring of the string s that contains at least two consecutive duplicates of the base string b is said to be repeating tandemly (nonoverlapping). Create and put into use an algorithm that, given two strings b and s, returns the index of the first tandem repetition of b in s. For instance, when b is abcab and s is abcabcababcababcababcab, your application should output 3.