Help a linguist to compare pairs of corresponding words in two languages! When c
ID: 3760403 • Letter: H
Question
Help a linguist to compare pairs of corresponding words in two languages! When comparing two corresponding words, such as "laugh" and "lachen," the linguist tries to match the two words letter by letter. She does not simply compare the words as they are. For the best match, before comparing the words, she inserts spaces into carefully chosen positions in both words, and in such a manner that the resulting stings acquire the same length. For instance, her choices might result in the strings "la_ugh_" and "lac_hen." When evaluating the match between "la_ugh_" and "lac_hen" she computes Sum_i F(v_i,w_i). Here v_i and w_i are the ith letters of the respective strings and F(A,B) is a function defined on pairs whose components come from {'a','b','c',...,'z','_'}. This F is known to her (i.e. given in advance). [For motivation, F(A,B) gives a large penalty if A has no tendency to transform into B; a smaller penalty if such transformation is more common; zero penalty if A=B.] For instance, if F(l,l)=0, F(a,a)=0, F(_,c)=1, F(u,_)= 2, F(g,h)=1, F(h,e)=3 and F(_,n)=2, then the above way of trying to mach laugh and lachen gets a score of 0+0+1+2+1+3+2=9. The similarity score of the (laugh,lachen) pair is however not 9, but rather the penalty score when the underscores are optimally placed in the two words (optimal = when the penalty score is minimized).
Input: A pair v, w of words and a function F: {'a','b','c',...,'z','_'} x {'a','b','c',...,'z','_'} -> non-negative integers (for computer scientists: int F[27][27]).
Output: The similarity score of the (v,w) pair [i.e. the penalty-sum under the optimal placing of the underscores (for explanation see above)].
Explanation / Answer
int Sum_i(int F[][27], string a, string b){
int sum = 0;
for(int i = 0; i < a.size(); i++){
int x, y;
if(a[i] >= 'a' && a[i] <= 'b'){
x = a[i] - 'a';
}
else x = 26;
if(b[i] >= 'a' && b[i] <= 'b'){
y = b[i] - 'a';
}
else y = 26;
sum += F[x][y];
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.