Write a program in C: The program shows the string alignment and the cost per al

Question

Write a program in C: The program shows the string alignment and the cost per aligned/matched pair between two input strings. Your solution can be either recursive or iterative. Hint: Remember that the alignment can be longer than the longest string! For example the best alignment between strings: abcdefghijk cdXYZefgh is: abc---defghijk --cXYZdefgh--- This alignment has cost 8. A pair of strings could have several different alignments that have the optimal cost and therefore are all correct answers. Any one of the alignments will be considered correct and sufficient (you do NOT need to list all of them or a specific one). See below and example of 2 different possible alignments. For the 'cat' and 'cs' strings there are two possible alignments, one alignment is: c a t c s - . x x another alignment is: c a t c - s . x x Either alignment will be considered correct. They depend on what you use as the minimum when 2 or all 3 distances are equal to the minimum distance. The 3-rd string shows the cost for each pair. A dot represents a cost of 0 and an x represents a cost of 1 (insert/delete/change). (The number of x-es shown must equal the edit distance between the strings. In this example the edit distance between "cat" and "cs" is 2 (it matches the distance in the bottom right corned of the distance table).)

Explanation / Answer

Before Going to the program, Let us first discuss about certain things here:

1) what is edit distance ?

Edit distance is counting the minimal number of process(insert/delete/change)needed while converting one string to another string.It is also called Levenshtein distance.

2) What is edit distance table ?

Edit distance table is arranging the values analysed during the edit distance calculation.

Now,Let us solve in detail about the answer:

The Levenshtein distance between "cat" and "cs" is 2.

Thus, the edit distance between these two strings is 2 and hence proved.

The total cost per aligned string is :3,

Let us discuss about the edit distance table(as discussed in your question :- In this example the edit distance between "cat" and "cs" is 2 (it matches the distance in the bottom right corned of the distance table)

In the below table you can find that,the condition is satisfied.

-

0

c

s

0

0

1

2

c

1

0

1

a

2

1

1

t

3

2

2

The Edit Distance between 'cat' and 'cs' is 2 (as mentioned earlier)

take the string 1- cat on the vertical division of the table, string 2 - cs on the horizontal division of the table and index both first row and column as '0'(Zero)

now take the values in the table that are bold and underlined.

0,0,1,2

in the first row, first column no operation happened so it : 0(Zero)

in the second row,second column value is 0(Zero) ( becus during the operation C holds the first position , so both C's are in 0 )

in the third row, second column value is 1( because, the 'a' was deleted/removed)

in the fourth row,third column value is 2 (because, 'S' was subsituted instead of 't')

here is the guide, how to proceed with the program:

string 1 - cat (A)

string 2 - cs (B)

1) Find if A can be changed to B or not by first creating a array for all characters of A, then checking with B if B has same count for every character.

2) Initialize result as 0.

3) Start traversing from end of both strings.(Because traversal can happen from both ends)
a) If current characters of A and B match, i.e., A[i] == B[j]
then do i = i-1 and j = j-1
b) If current characters don’t match, then search B[j] in remaining A.

While searching, keep incrementing result as these characters must be moved ahead for A to B strings in the result.

Using the given algorithm, you can try out the program in C.

-

0

c

s

0

0

1

2

c

1

0

1

a

2

1

1

t

3

2

2

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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