Write the algorithm and calculate its running time Please use the appropriate no

Question

Write the algorithm and calculate its running time Please use the appropriate notations and please explain thoroughly,i really have a problem with understanding these(just dont answer if you dont want to explain)
also please make it readable
your help is very much appreciated Please use the appropriate notations and please explain thoroughly,i really have a problem with understanding these(just dont answer if you dont want to explain)
also please make it readable
your help is very much appreciated 15-2 Longest palindrome subsequence A palindrome is a nonempty string over some alphabet that reads the same for- ward and backward. Examples of palindromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes). Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac. What is the running time of your algorithm? ut string. For example, given the input ch.a

Explanation / Answer

We will form a 2d array that:

palindrome[i][j] = true, if from index i to index j, the substring is a palindrome

= false , otherwise

Main calculation:

palindrome[i][j] = (string[i] == string[j] ? plaindrome[i+1][j-1] : false)

Algorithm:

for(int i = 0; i < n; i++)

palindrome[i][i] = true

for(int i = 0; i < n-1; i++)

palindrome[i][i+1] = (str[i] == str[i+1])

for(int l = 3; l < n; l++)

for(int i = 0; i+l < n; i++)

j = i+l;

palindrome[i][j] = (string[i] == string[j] ? plaindrome[i+1][j-1] : false)

if(palindrome[i][j] == true)

res = max(res, j-i+1)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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