1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
DochEvi [55]
4 years ago
8

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all s

trings 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?
Computers and Technology
1 answer:
Vera_Pavlovna [14]4 years ago
7 0

Answer:

Algorithm:

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

L[i][i] = 1;

for (cl=2; cl<=n; cl++)

{

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

{

j = i+cl-1;

if (str[i] == str[j] && cl == 2)

L[i][j] = 2;

else if (str[i] == str[j])

L[i][j] = L[i+1][j-1] + 2;

else

L[i][j] = max(L[i][j-1], L[i+1][j]);

}

}

Time complexity:

O(n^2)

Explanation:

  • Run a for loop until i is less than n and assign a value of 1 to the L 2D array which is of size n*n while n being the length of the string.
  • Run a nested for loop and check if the value at ith and jth index of str input string is equal, and then assign the value of 2 to the L 2D array.
  • Otherwise choose the maximum value from within the 2D array using the max function.
  • As there is a nested loop used in this algorithm so the time complexity of the algorithm is O(n^2).
You might be interested in
Consider the following code snippet that appears in a subclass: public void deposit(double amount) { transactionCount ++; deposi
nasty-shy [4]
A is the answer I got a call back at the park today and then we walked in and got it to the park where the store got to
4 0
2 years ago
Complete the sentence.<br> Python is a_____<br> level language compared to bytecode.
Crazy boy [7]

Answer:

High

Explanation:

Python is high level; Bytecode is intermediate

5 0
3 years ago
Read 2 more answers
Your friends know that you understand a lot about computers, both the technical details of how they operate as well as informati
erma4kov [3.2K]

Answer:

The answer is A.

Explanation:

Regarding the information given in the question, we are asked to evaluate the options given which i believe have answers as follows;

B is true. Public-domain means that there are no individuals who hold a copyright over the subject which enables people to copy and distribute, the software in this case, freely.

C is true. Shareware is a term that is used for applications which have a certain trial period for users to decide whether the application meets their needs and demands and then they have to pay the required amount to keep using the software to its full potential. Most often it is the case that if the user does not agree to a payment, the features they are allowed to use are very limited and render the software almost useless until the payment is completed.

D is true. "Copyright" is by definition is approved by the authorities and gives its creater the right to use, sell and change the creative product as they please. It works the same way for software products as well so the statement in option D is true.

A is wrong. Although they are freeware, this softwares still may have copyrights and even if they do not, they are very basic or even incomplete programs to satisfy the minimal needs of its users.

I hope this answer helps.

7 0
3 years ago
Write a method for the Invitation class that accepts a parameter and uses it to update the address for the event.
DerKrebs [107]

Answer:

public class Invitation {

 private String hostname;

 private String address;

  public Invitation(String n, String a) {  // constructor that accepts two strings.

   hostname = n;

   address = a;

 }

  public String getHostname() {

   return hostname;

 }

 public void setAddress(String a) {

   address = a;

 }  

 public String invite(String guest) {

   return "Hello" +guest+ ", you are invited to my party at " +address+". "+hostname+".";

 }

 public Invitation(String host, String address) {

   this.address = address;

   this.hostname = host;

 }

}

Explanation:

The Java program defines a class called "Invitation". The class constructor has two string arguments or parameters for the host of the event and the address. The invite method is used to generate the string invite message with the name of the guest as the argument. Use the "setAddress" method to set a new location of the event and the "getHostname" to get the name of the event host.

6 0
3 years ago
Which type of information should never be given out on social media?
zhenek [66]

Answer:

Sites like Face.book are full of valuable data for people who use social engineering to steal your identity on social media. You should therefore avoid sharing information that's used to verify your identity,

Explanation:

7 0
3 years ago
Read 2 more answers
Other questions:
  • The _____ command icon looks like a small clipboard with a page attached.
    6·1 answer
  • Which type of security personnel may work for government as well as for private security agencies?
    7·2 answers
  • Consider the provided C++ code in the main.cpp file: The function func2 has three parameters of type int, int, and double, say a
    8·1 answer
  • Henry, a graphic artist, wants to create posters. Which software should Henry use for this purpose?
    13·1 answer
  • A type of Knowledge Management System is called
    5·1 answer
  • Pick one of the following scenarios and
    6·1 answer
  • There is a file of a few Sean Connery movies on the internet. Each entry has the following form:
    9·1 answer
  • NEED HELP ASAP!!!!!!
    7·2 answers
  • EASY What does the Backspace key do?
    6·1 answer
  • Which feature is not in ms PowerPoint​
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!