164 - String Computer

yiuyuho · Post by **yiuyuho** » Tue Apr 22, 2003 3:51 pm

cannot reconstruct solution? How do you calculate the minimum distance?

Maxim · Post by **Maxim** » Tue Apr 22, 2003 7:29 pm

It is needed two-dimensional integer array, say S. After computation, S[m][n] is minimum distance, where m is length of s1 (first string) and n length of s2 (second string). Here is how I do computation:

val = (s1 == s2[j]) ? 0 : 1;
S[j] = min( S[i-1][j-1] + val, S[i-1][j]+1 , S[j-1]+1 );

yiuyuho · Post by **yiuyuho** » Tue Apr 22, 2003 7:52 pm

Levenstein Distance, you understand how and why it works?

Maxim · Post by **Maxim** » Tue Apr 22, 2003 9:03 pm

Yes, I do. I'm not total newbie to DP as I seem to be.

Still puzzled about outputting...

Maxim

yiuyuho · Post by **yiuyuho** » Tue Apr 22, 2003 9:48 pm

ok then,
let f as source str, t as target string,

to back track:
start from s[m][n], m= len(to), n=len(from)
if(s[m][n]==0) then done
else
compare and found where s[m][n] is from:

again set val = (s[m]==s[n]?0:1)
now, if(s[m][n]==s[m-1][n]+1),
this means you can transform from
f(0..n) to t(0..m-1) using s[m-1][n] operations, so you can do that and than insert t[m] to t(0..m-1). of course you can also first insert t[m] to f(0..n) then transform from f(0..n) to t(0..m-1), and t[m] will append at the end anyways. Set m:=m-1 after operation

similarly, if(s[m][n]==s[m][n-1]+1) refers to a delete at f[n] rather than insert at t in the previous case.

and s[m][n]==s[m-1][n-1]+val refers to a change f val = 1 and no operation when val = 0

yiuyuho · Post by **yiuyuho** » Tue Apr 22, 2003 9:49 pm

But, as I said somehow strangely the judge only accept back track in certain order, whiuch I haven't figure why yet.

Observer · Post by **Observer** » Thu Jul 24, 2003 8:01 am

Can anyone help me on the output part?

We've to output the position of "changed characters", but as the position of characters will be changed whenever Insert/Delete function is called, what shall we do?

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jul 24, 2003 8:22 am

you must handle it by hand. If I correct remmber I use something like this:
1. if operation == DELETE do nothing
2. if operation == INSERT do pos++
3. if operation == CHANGE do pos++

Best ragards
DM

anupam · Post by **anupam** » Thu Jul 24, 2003 8:56 am

the book of clrs may help you...

Observer · Post by **Observer** » Thu Jul 24, 2003 8:59 am

Dominik Michniewski wrote:you must handle it by hand. If I correct remmber I use something like this:
1. if operation == DELETE do nothing
2. if operation == INSERT do pos++
3. if operation == CHANGE do pos++

Best ragards
DM

Could you explain a bit further plz?? Why DELETE == do nothing?

P.S. I've no trouble finding the "edit distance"...

anupam · Post by **anupam** » Thu Jul 24, 2003 9:01 am

There is a similar problem in the volumes but i can't remember.
plz help

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jul 24, 2003 1:28 pm

When you delete character from input string, position which you must output doesn't change.

Anupam: yes, in volumes exists other problem in this manner - 52x or something like this ...

Best regards
DM

Observer · Post by **Observer** » Wed Aug 20, 2003 2:38 am

I don't understand...

I got ACC for problem 526, but not this one!!!! Why? Aren't them identical???? Plz help!!!

Observer · Post by **Observer** » Wed Aug 20, 2003 3:11 am

Finally got ACC. As yiuyuho has mentioned before, the judge only accept back track in certain order.

I used D-C-I and got WA.
Changed to C-D-I and got ACC!!!! Strange...

youquan · Post by **youquan** » Sat Sep 13, 2003 7:54 pm

I think it has got to do with the limit of the strings being 20... if you track in certain order, some of them would give numbers which are beyond 20... like if you track for insert first, then you delete... then you might insert letters beyond the limit of 20 and then delete whatever you want to delete... which is probably what is causing all the WA...