GATE CSE
First time here? Checkout the FAQ!
x
0 votes
18 views

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}$.

(1)

oc-urr-ance

occurre-nce

(2)

ct-at-g-

-tta-agc

(3)

ctat---g-

---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 (92.6k points) 975 2337 3116 | 18 views

Please log in or register to answer this question.



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
Top Users Oct 2017
  1. Arjun

    23438 Points

  2. Bikram

    17108 Points

  3. Habibkhan

    8354 Points

  4. srestha

    6314 Points

  5. Debashish Deka

    5458 Points

  6. jothee

    5008 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4390 Points

  9. sushmita

    3996 Points

  10. Rishi yadav

    3846 Points


Recent Badges

Popular Question sunil sarode
Verified Human nandisrinivas
Nice Question shraddha priya
Popular Question just_bhavana
Famous Question rahul sharma 5
Popular Question Jithin Jayan
Great Answer Sankaranarayanan P.N
Good Question jothee
Great Answer Sankaranarayanan P.N
Famous Question pC
27,346 questions
35,201 answers
84,230 comments
33,327 users