The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

An automatic spelling checker works as follows. Given a word $w$, first check if $w$ is found in the dictionary. If $w$ is not in the dictionary, compute a dictionary entry that is close to $w$. For instance if the user types $\mathsf{ocurrance}$, the spelling checker should suggest $\mathsf{occurence}$, which belongs to the dictionary. Similarity between words such as $\mathsf{occurrence}$ and $\mathsf{occurrance}$ is quantified in terms of $alignment$.

An alignment between two strings $w1$ and $w2$ (over the alphabet $\{ \mathsf{a, b, c, ...., z} \}$) is obtained by inserting hyphens in the two strings such that the modified strings $align$ (i.e.,the modified strings are of equal length, and at each position, either both strings have the same letter or one of the strings has a hyphen).

here are three examples of alignments. The first is between $\mathsf{ocurrance}$ and $\mathsf{occurrence}$ and the second and third are between $\mathsf{ctatg}$ and $\mathsf{ttaagc}$.










A $mismatch$ in an alignment is a position where one of modified strings has  a hyphen and the other does not. There are three mismatches in the first alignment given above, five mismatches in the second, and seven mismatches in the third.

use dynamic programming to give an efficient algorithm that takes two strings $x$ and $y$ (over teh alphabet $\{ \mathsf{a, b, c, ... , z} \}$ as its input, and computes the minimum number of mismatches among all alignments of $x$ and $y$. What is the running time of your algorithm (in terms of the lengths of $x$ and $y$)?

asked in Others by Veteran (116k points) | 52 views

1 Answer

0 votes

let us store element of w1 in the array a[w1] and that of w2 in array b[w2] let C[w1*w2] be our new array where we sore results 


1$\leq i\leq w1$ 1$\leq j\leq w2$  C[i-1,j-1]=0

c[i][j]=$\left\{\begin{matrix} c[i-1,j-1]& a[i]=b[j], i=j\\ 1+c[i-1,j-1] & a[i]="-",b[j]="-",a[i]!=b[j],i=j\\ c[i-1,j]& i<j\\ 0 & i>j\\ c[i-1,j-1] & otherwise \end{matrix}\right.$ 

answer will be last entry c[w1,w2]

eg let

w1= t-sl-


  t - s l -
- 1 1 1 1 1
e 0 2 2 2 2
s 0 0 2 2 2
- 0 0 0 3 3
a 0 0 0 0 4

minimum mismatch is 4 

Time Complexiy is O(w1*w2)

answered by Boss (18.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,443 questions
53,648 answers
70,909 users