Consider the ab-Search problem, which takes an input string data of length n and

Question

Consider the ab-Search problem, which takes an input string data of length n and identifies the first instance of the substring ab in data(or -1 if data does not contain ab). Formally: If we take an input array data and divide it in half (data[1 mid] abd da[nud + 1 n], where mid = [n/2]), ab coukl be in the left half, it could be in the right half, or it could be between the two halves. Write 2-3 function calls that represent these three cases. What is the base case for ab searching? (Multiple correct answers) Write a divide-and-conquer algorithm that solves the ab-searching problem. Be sure to consider: how you solve the base case, how you construct the solution of the problem on the basis of the three cases listed in problem 1, including the case where ab is "missing."

Explanation / Answer

function(data, n):

if(n == 2){

if(data[0] == 'a' && data[1] == 'b')

return 0

else

return -1;

}

int mid = n/2

left = function(1,mid)

if (left == -1)

{

right = function(data[mid+1:], n-mid)

if(right == -1)

{

between= function(data[mid:mid+1], 2)

if(between == -1) return -1

else

return mid
}

return right+mid;

}

return left

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.