GATE CSE
First time here? Checkout the FAQ!
x
0 votes
12 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 (77.2k points)   | 12 views

Please log in or register to answer this question.



Top Users May 2017
  1. akash.dinkar12

    3154 Points

  2. pawan kumarln

    1636 Points

  3. sh!va

    1600 Points

  4. Arjun

    1360 Points

  5. Bikram

    1322 Points

  6. Devshree Dubey

    1262 Points

  7. Debashish Deka

    1132 Points

  8. Angkit

    1044 Points

  9. LeenSharma

    900 Points

  10. srestha

    710 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    408 Points

  2. pawan kumarln

    262 Points

  3. Ahwan

    236 Points

  4. Arnab Bhadra

    234 Points

  5. LeenSharma

    138 Points


22,772 questions
29,098 answers
65,132 comments
27,639 users