contestada

Dr. Watson has been kidnaped! Sherlock Holmes was contacted by the kidnapper for ransom. Moments later he received a message from Dr. Watson's phone. The message contained three random strings. Sherlock being Sherlock, was able to deduce immediately that Dr. Watson was trying to give a hint about his location. He figured out that the longest common subsequence between the 3 words is the location. But since it was too easy for him, he got bored and asked you to find out what the actual location is. Your task is to find the longest common subsequence from the 3 given strings before it is too late. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For instance, given a sequence "drew"; "d", "w", "de", "drw", "drew" are all examples of valid subsequences (there are also others), while "er", "wdre" are not. Design a dynamic programming algorithm which takes three input sequences X, Y, and Z, of lengths m, n, and p, respectively, and returns their longest common subsequence. For full marks your algorithm should run in (mnp) time. Note that W is a common subsequence of X, Y, and Z if and only if W is a subsequence of X, W is a subsequence of Y, and W is a subsequence of Z.

Required:
Describe the set of subproblems that your dynamic programming algorithm will consider.

Respuesta :

sk5634943

Answer:

please mark me brainlist

Explanation:

This algorithm works for n number of strings in python3

Input:

83217

8213897

683147

Output:

837

from itertools import product

import pdb

import numpy as np

def neigh(index):

N = len(index)

for ri in product((0, -1), repeat=N):

if not all(i == 0 for i in ri):

yield tuple(i + i_rel for i, i_rel in zip(index, ri))

def longestCommonSubSequenceOfN(sqs):

numberOfSequences = len(sqs); # to know number of sequences

lengths = np.array([len(sequence) for sequence in sqs]); # to know length of each sequences placed in # array

incrLengths = lengths + 1; # here we are taking no .of sequences +1

lengths = tuple(lengths); # making lengths into tuple to make it mutable

inverseDistances = np.zeros(incrLengths);

ranges = [tuple(range(1, length+1)) for length in lengths[::-1]]; # finding ranges from 1 to each lengths

for tupleIndex in product(*ranges):

tupleIndex = tupleIndex[::-1];

neighborIndexes = list(neigh(tupleIndex)); # finding neighbours for each tupled index value and # store them in list

operationsWithMisMatch = np.array([]); # creating array which are miss matched

 

for neighborIndex in neighborIndexes:

operationsWithMisMatch = np.append(operationsWithMisMatch, inverseDistances[neighborIndex]);

#appending newly created array with operations miss match and inverseDistances

operationsWithMatch = np.copy(operationsWithMisMatch);

# copying newly generated missmatch indexs

operationsWithMatch[-1] = operationsWithMatch[-1] + 1;

# incrementing last indexed value

chars = [sqs[i][neighborIndexes[-1][i]] for i in range(numberOfSequences)];

# finding a string(chars) with neighbour indexes and checking with other sequences

if(all(elem == chars[0] for elem in chars)):

inverseDistances[tupleIndex] = max(operationsWithMatch);

else:

inverseDistances[tupleIndex] = max(operationsWithMisMatch);

 

subString = ""; # resulted string

mainTupleIndex = lengths; # copying lengths list to mainTupleIndex

while(all(ind > 0 for ind in mainTupleIndex)):

neighborsIndexes = list(neigh(mainTupleIndex));

#generating neighbour indexes with main tuple index in form of list

anyOperation = False;

for tupleIndex in neighborsIndexes:

current = inverseDistances[mainTupleIndex];

if(current == inverseDistances[tupleIndex]): # comparing indexes in main tuple index and inverse #distance tuple index

mainTupleIndex = tupleIndex;

anyOperation = True;

break;

if(not anyOperation): # if anyoperation is False then we are generating sunString

subString += str(sqs[0][mainTupleIndex[0] - 1]);

mainTupleIndex = neighborsIndexes[-1];

return subString[::-1]; # reversing resulted string

sequences = ["83217", "8213897", "683147"]

print(longestCommonSubSequenceOfN(sequences)); #837

Otras preguntas