526 - String Distance and Transform Process

[magnus]

Does anybody have suggestions for what the traps are in this problem?
There has been no success getting past a WA reply.

thx in advance,

Magnus

[little joey]

There are no traps. Carefully read the input specification. Don't use the wrong function when you program in C.

[magnus]

Thanks, but would you care to expand on this.

Magnus

[Caesum]

I am AC on this, just a couple of days ago, try this input:

Pabdaeafcfbfeecfcbdfecfebdbdaafcfcefcfdfbeaffd
Dcabfbedbabcdfceccbdcbcfbedbbcbaaddffecddbcfdfef

My output is:

29
1 Replace 46,f
2 Replace 45,e
3 Replace 43,d
4 Replace 42,f
5 Replace 41,c
6 Replace 40,b
7 Replace 38,d
8 Delete 36
9 Replace 34,f
10 Replace 32,d
11 Replace 31,d
12 Replace 28,b
13 Replace 27,c
14 Replace 26,b
15 Insert 25,d
16 Insert 24,b
17 Replace 21,b
18 Replace 20,c
19 Delete 16
20 Replace 13,c
21 Replace 11,d
22 Delete 10
23 Replace 8,b
24 Insert 7,b
25 Insert 7,d
26 Replace 5,b
27 Replace 4,f
28 Replace 1,c
29 Insert 1,D

[little joey]

I'm also AC on this, also a couple of days ago, but that's not what I meant.
Consider the input

Code: Select all

"Tomorrow "
"no sorrow"
"Tomorrow"
"no sorrow"

without the quotes, they are only there to illustrate my point, which gives

Code: Select all

4
1 Replace 1,n
2 Replace 3, 
3 Insert 4,s
4 Delete 10

3
1 Replace 1,n
2 Replace 3, 
3 Insert 4,s

Most people will miss this subtlety, although they get AC.

[Caesum]

Actually I spot it:

4
1 Delete 9
2 Replace 3,s
3 Insert 3,
4 Replace 1,n

3
1 Replace 3,s
2 Insert 3,
3 Replace 1,n

but I see what you mean, yes

[little joey]

That would be a nice challenge: How many minimum length sequences are there for a given transformation? Haven't thought about it jet, so the answer could be trivial, although I don't think so.

Sure your program spots it, wouldn't get AC otherwise. The question is, did you consider the possibility when you wrote it. If you use the wrong function to read the input, you'll never get AC.

Just gave it a little thought. It's counting paths, I think.

[magnus]

Thanks, you were right; it was the non-character input that was
causing problems.

Cheers,

Magnus

[tone4]

can you give me some idea ?
or tell me where i can find the anser to similar problem

thx

[little joey]

You could look for "approximate string matching" using Google, or an other search engine.

I found http://www-apparitions.ucsd.edu/~rmckinle/string/ which gives a Java animation of the DP-implementation, a brief explanation and the source code.

It probably takes some re-reading and pen-and-paper animation before you grab the method, but it's worth the wile.

Good luck.

[turuthok]

You can also search in Google using keyword "Levenshtein" ... the very first link in the search-result itself is enough.

-turuthok-

[tone4]

thank you very much

i learn something again

thx

[tone4]

the inputs of this question contains blank line,

remember to use gets(str); to read a input string

[Subeen]

I am getting WA with my program. Please give me some sample input for which my program fails.
Here is my code:
[cpp]#include <stdio.h>
#include <string.h>

#define MATCH 0
#define INSERT 1
#define DELETE 2

#define MAXLEN 85

typedef struct
{
int cost;
int parent;
}cell;

cell m[MAXLEN+1][MAXLEN+1];

int match(char c, char d)
{
if(c==d) return 0;
return 1;
}

void row_init(int i)
{
m[0].cost = i;
if(i > 0) m[0].parent = INSERT;
else m[0].parent = -1;
}

void column_init(int i)
{
m[0].cost = i;
if(i > 0) m[0].parent = DELETE;
else m[0].parent = -1;
}

int string_compare(char *s, char *t)
{
int i, j, k;
int opt[3]; /* cost of the three operations */

for(i=0; i<MAXLEN; i++)
{
row_init(i);
column_init(i);
}

for(i=1; i<strlen(s); i++)
{
for(j=1; j<strlen(t); j++)
{
opt[MATCH] = m[i-1][j-1].cost + match(s, t[j]);
opt[INSERT] = m[j-1].cost + 1;
opt[DELETE] = m[i-1][j].cost + 1;

m[j].cost = opt[MATCH];
m[j].parent = MATCH;
for(k=INSERT; k<=DELETE; k++)
{
if(opt[k] < m[i][j].cost)
{
m[i][j].cost = opt[k];
m[i][j].parent = k;
}
}
}
}
return m[i-1][j-1].cost;
}

int count;

void reconstruct_path(char *s, char *t, int i, int j)
{
if(m[i][j].parent == -1) return;

if(m[i][j].parent == MATCH)
{
reconstruct_path(s, t, i-1, j-1);
if(s[i]!=t[j])
printf("%d Replace %d,%c\n", count++, j, t[j]);
return;
}

if(m[i][j].parent == INSERT)
{
reconstruct_path(s, t, i, j-1);
printf("%d Insert %d,%c\n", count++, j, t[j]);
return;
}

if(m[i][j].parent == DELETE)
{
reconstruct_path(s, t, i-1, j);
printf("%d Delete %d\n", count++, i);
return;
}
}

int main()
{
char s[MAXLEN], t[MAXLEN], a[MAXLEN];
int cost, f=0;

memset(s, 0, sizeof(s));
memset(t, 0, sizeof(t));
memset(a, 0, sizeof(a));
while(gets(s))
{
t[0] = ' ';
strcat(t, s);
strcpy(s, t);
if(!gets(a)) break;
t[0] = ' ';
t[1] = 0;
strcat(t, a);
cost = string_compare(s, t);
if(f) printf("\n");
else f = 1;
printf("%d\n", cost);
count = 1;
if(cost > 0)reconstruct_path(s, t, strlen(s)-1, strlen(t)-1);
memset(s, 0, sizeof(s));
memset(t, 0, sizeof(t));
memset(a, 0, sizeof(a));
}
}[/cpp]

[worldguy]

I passed 164 but failed at this problem. I generated some test data, followed by output. The output was checked by a program(by me), which is performing these operations on the input string and sees if the result is expected. I've no idea what's wrong with the program.

Any suggestions would help!

Code: Select all

sfkgphrdbufoihecwuulkhmce
ihyenlssxuyibv
pydpdhxbsyuygkkytwwqrtcmp
jwmgoetjsgubyqfloisqkhsjoxfclkjbcnfndgfniatsq
nqafjgijuaosagzxydtkhutnlmodzwmjxbttfgqkwvzgpgazeflsudbaicf
ayzztgwrhwvqycnviklffzlf
hqmuhyzdlkzhwbbazonwkjabfiwvjqodqqydstdshaefjlcwscbq
xluxteuyteiaicnozjrepzjownwlmmisxlpm
mmzurnqzkvjkfqfk
kdququeqxmdhcptihrugapazdlvywiayhc
cojwnqejprotvnfhdzpuwqvmknbesconoepfan
ycfnjmnbupqgmfitogkgeikdjbmhjutakayxsuvppftefdstcztgqylc
jymzuokcwbtuvtbpxebztswbqzuwtdpl
mrsqcajnntkxtafipjpnsoojmcegickzenrqvgztitzebpuauunizj
gqkdamokjht
dfcepspmctodscokhsojeec
olrkstkqmqdcuarkzjpmhnfcoxotwhxtkqxdrbnjafyhqzqeiyfql
nqsbnuflmwubmaboikjwh
shljceaxnuvbgijvhtbnrdjeepzahqwhhrqfulkremunaeupbfujgx
epjgjweinfh
babdxsqibobwnoxtvlxmohqussqpoefwekqsugzfhvjcculqipnmpun
szalstngjfcektvgkiudfvnaexfrhnpottlkkhfktkrxrhdbes
busruurhmmzameikztjjuvyf
mpbqudliuwnkwgouvgrsvylhhzn
mtgqejpddhxwyqfgbwmphoghxyxkcmcqcopndjvzxubq
uspvyfhiapcin
grvmzeyqyalzhjnjbakilwbuawfrkzkutmkixozd
kwlrhmdjyayoahzrqgoeztxikgdkhqcdswrbuztmiopjwheaajdfpaf
kzjhhhpxhvkpcrtmmijyauptjceekcalbced
qepryqaiwdcrsomakptfbeemcopmohyskfjwqibnhtqjmxhupchuqtccx
ssdjmkzpqztfygf
azexlvdavq
jaczqpgnoombwuucthqkorbzqjerolbugypgviq
bwyuejkwiesfbudanjmzedclmuxguftyyabnb
ufrqbjjjtwejwvkcmegblvntffjgftpjdkjtlfiiizr
miyfarvospeeuzihtegqmwwrnnewehgakxqzgkbrgurvtw
rgrkkexzzortnbhxlralzrvnsgyuwrwkybh
zqzsapufpnqueddahivhpcj
taqvaxwpdklnyjzberdgbflljuvntjqdlqvlnqxhzp
ipjixbdkhf
jhceaxihcxaecmezebpejfzsigfxkmmrmu
gwfqdqgfidtio
nfkzaujktqraycjxeqdhlqggqstypyhqdraaduqasuuwjaomzr
uqdtgxtgzqynudhjirbcb
xkpnuttjpsyqbzzdlgueeprzqyiobfqxwslsvazucpfmiocuqspmh
cdlofgutpy
ymyfazjqnyrrpywyvrrblzapnjfgvdbgrhwwxscsdqlicoc
gftigeqaqlfwkl
aqqabkikssfgdigclbwljfab
ruifajammrayudqiiyhmlulkxuxylbfx

Here is my output data:

Code: Select all

23
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Replace 1,i
6 Delete 3
7 Delete 3
8 Delete 3
9 Delete 3
10 Delete 3
11 Delete 3
12 Delete 3
13 Replace 3,y
14 Replace 5,n
15 Replace 6,l
16 Replace 7,s
17 Replace 8,s
18 Replace 9,x
19 Replace 10,u
20 Replace 11,y
21 Replace 12,i
22 Replace 13,b
23 Replace 14,v

40
1 Replace 1,j
2 Replace 2,w
3 Replace 3,m
4 Replace 4,g
5 Replace 5,o
6 Replace 6,e
7 Replace 7,t
8 Replace 8,j
9 Replace 10,g
10 Insert 12,b
11 Insert 14,q
12 Insert 15,f
13 Insert 16,l
14 Insert 17,o
15 Insert 18,i
16 Insert 19,s
17 Replace 20,q
18 Insert 22,h
19 Insert 23,s
20 Insert 24,j
21 Insert 25,o
22 Insert 26,x
23 Insert 27,f
24 Insert 28,c
25 Insert 29,l
26 Insert 31,j
27 Insert 32,b
28 Insert 33,c
29 Insert 34,n
30 Insert 35,f
31 Replace 36,n
32 Replace 37,d
33 Replace 38,g
34 Replace 39,f
35 Replace 40,n
36 Replace 41,i
37 Replace 42,a
38 Replace 43,t
39 Replace 44,s
40 Replace 45,q

51
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Delete 1
6 Delete 1
7 Delete 1
8 Delete 1
9 Delete 1
10 Delete 1
11 Delete 1
12 Delete 1
13 Delete 2
14 Delete 2
15 Delete 2
16 Delete 3
17 Delete 3
18 Delete 3
19 Delete 3
20 Delete 3
21 Delete 3
22 Delete 3
23 Delete 3
24 Delete 3
25 Delete 3
26 Delete 3
27 Delete 4
28 Delete 4
29 Delete 4
30 Delete 4
31 Delete 4
32 Replace 4,z
33 Replace 6,g
34 Replace 7,w
35 Replace 8,r
36 Replace 9,h
37 Delete 12
38 Replace 12,q
39 Replace 13,y
40 Replace 14,c
41 Replace 15,n
42 Replace 16,v
43 Replace 17,i
44 Replace 18,k
45 Delete 20
46 Delete 20
47 Delete 20
48 Replace 20,f
49 Replace 21,f
50 Replace 22,z
51 Replace 23,l

44
1 Delete 1
2 Replace 1,x
3 Replace 2,l
4 Delete 4
5 Delete 4
6 Delete 4
7 Replace 4,x
8 Replace 5,t
9 Replace 6,e
10 Replace 7,u
11 Replace 8,y
12 Replace 9,t
13 Replace 10,e
14 Replace 11,i
15 Replace 13,i
16 Replace 14,c
17 Replace 16,o
18 Replace 17,z
19 Delete 19
20 Delete 19
21 Replace 19,r
22 Replace 20,e
23 Replace 21,p
24 Replace 22,z
25 Delete 24
26 Delete 25
27 Replace 25,w
28 Replace 26,n
29 Replace 27,w
30 Replace 28,l
31 Replace 29,m
32 Replace 30,m
33 Replace 31,i
34 Delete 33
35 Delete 33
36 Delete 33
37 Delete 33
38 Replace 33,x
39 Delete 35
40 Delete 35
41 Delete 35
42 Delete 35
43 Replace 35,p
44 Replace 36,m

30
1 Insert 1,k
2 Insert 2,d
3 Insert 3,q
4 Insert 4,u
5 Insert 5,q
6 Insert 6,u
7 Insert 7,e
8 Insert 8,q
9 Insert 9,x
10 Insert 11,d
11 Insert 12,h
12 Insert 13,c
13 Insert 14,p
14 Insert 15,t
15 Insert 16,i
16 Replace 17,h
17 Replace 18,r
18 Insert 20,g
19 Replace 21,a
20 Replace 22,p
21 Replace 23,a
22 Insert 25,d
23 Replace 26,l
24 Insert 28,y
25 Replace 29,w
26 Replace 30,i
27 Replace 31,a
28 Replace 32,y
29 Replace 33,h
30 Replace 34,c

46
1 Insert 1,y
2 Insert 3,f
3 Replace 4,n
4 Replace 6,m
5 Insert 8,b
6 Insert 9,u
7 Insert 10,p
8 Insert 12,g
9 Replace 13,m
10 Replace 14,f
11 Replace 15,i
12 Replace 16,t
13 Insert 18,g
14 Replace 19,k
15 Replace 20,g
16 Replace 21,e
17 Replace 22,i
18 Replace 23,k
19 Insert 25,j
20 Insert 26,b
21 Insert 27,m
22 Replace 28,h
23 Replace 29,j
24 Insert 31,t
25 Insert 32,a
26 Insert 33,k
27 Insert 34,a
28 Insert 35,y
29 Insert 36,x
30 Replace 37,s
31 Replace 38,u
32 Replace 40,p
33 Replace 41,p
34 Replace 42,f
35 Replace 43,t
36 Insert 45,f
37 Insert 46,d
38 Replace 48,t
39 Replace 49,c
40 Replace 50,z
41 Replace 51,t
42 Replace 52,g
43 Replace 53,q
44 Replace 54,y
45 Replace 55,l
46 Replace 56,c

47
1 Insert 1,m
2 Insert 2,r
3 Insert 3,s
4 Insert 4,q
5 Insert 5,c
6 Insert 6,a
7 Insert 7,j
8 Insert 8,n
9 Insert 9,n
10 Insert 10,t
11 Insert 11,k
12 Insert 12,x
13 Insert 13,t
14 Insert 14,a
15 Insert 15,f
16 Insert 16,i
17 Insert 17,p
18 Replace 19,p
19 Replace 20,n
20 Replace 21,s
21 Replace 22,o
22 Insert 24,j
23 Replace 25,m
24 Insert 27,e
25 Replace 28,g
26 Replace 29,i
27 Replace 30,c
28 Replace 31,k
29 Replace 32,z
30 Replace 33,e
31 Replace 34,n
32 Replace 35,r
33 Replace 36,q
34 Replace 37,v
35 Replace 38,g
36 Insert 40,t
37 Insert 41,i
38 Replace 43,z
39 Replace 44,e
40 Insert 46,p
41 Replace 47,u
42 Replace 48,a
43 Replace 50,u
44 Replace 51,n
45 Replace 52,i
46 Replace 53,z
47 Replace 54,j

19
1 Insert 1,d
2 Insert 2,f
3 Insert 3,c
4 Insert 4,e
5 Insert 5,p
6 Insert 6,s
7 Insert 7,p
8 Insert 8,m
9 Replace 9,c
10 Replace 10,t
11 Replace 11,o
12 Replace 13,s
13 Replace 14,c
14 Insert 17,h
15 Insert 18,s
16 Insert 19,o
17 Insert 21,e
18 Replace 22,e
19 Replace 23,c

46
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Delete 1
6 Delete 1
7 Replace 1,n
8 Delete 3
9 Replace 3,s
10 Replace 4,b
11 Replace 5,n
12 Delete 7
13 Delete 7
14 Delete 7
15 Delete 7
16 Delete 7
17 Delete 7
18 Delete 7
19 Delete 7
20 Delete 7
21 Delete 8
22 Delete 8
23 Delete 8
24 Replace 8,l
25 Replace 9,m
26 Delete 11
27 Delete 11
28 Delete 11
29 Delete 11
30 Delete 11
31 Delete 11
32 Delete 11
33 Replace 11,u
34 Delete 13
35 Replace 13,m
36 Delete 15
37 Delete 15
38 Delete 15
39 Delete 15
40 Delete 15
41 Replace 15,b
42 Replace 16,o
43 Replace 18,k
44 Replace 19,j
45 Replace 20,w
46 Replace 21,h

47
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Delete 1
6 Delete 2
7 Delete 2
8 Delete 2
9 Delete 2
10 Delete 2
11 Delete 2
12 Delete 2
13 Replace 2,p
14 Delete 4
15 Delete 4
16 Delete 4
17 Delete 4
18 Delete 4
19 Delete 4
20 Replace 4,g
21 Delete 6
22 Delete 6
23 Delete 6
24 Delete 6
25 Delete 6
26 Delete 6
27 Delete 6
28 Delete 7
29 Delete 7
30 Delete 7
31 Delete 7
32 Delete 7
33 Delete 7
34 Delete 7
35 Delete 7
36 Delete 7
37 Delete 8
38 Replace 8,i
39 Delete 10
40 Delete 10
41 Delete 10
42 Delete 10
43 Delete 10
44 Delete 11
45 Delete 11
46 Delete 11
47 Replace 11,h

50
1 Delete 1
2 Replace 1,s
3 Replace 2,z
4 Replace 3,a
5 Replace 4,l
6 Delete 6
7 Replace 6,t
8 Replace 7,n
9 Replace 8,g
10 Replace 9,j
11 Replace 10,f
12 Replace 11,c
13 Replace 12,e
14 Replace 13,k
15 Delete 16
16 Delete 16
17 Delete 16
18 Replace 16,g
19 Replace 17,k
20 Replace 18,i
21 Replace 20,d
22 Replace 21,f
23 Replace 22,v
24 Replace 23,n
25 Replace 24,a
26 Replace 26,x
27 Replace 27,f
28 Replace 28,r
29 Replace 29,h
30 Replace 30,n
31 Replace 31,p
32 Replace 32,o
33 Replace 33,t
34 Replace 34,t
35 Replace 35,l
36 Replace 36,k
37 Replace 37,k
38 Replace 38,h
39 Replace 39,f
40 Replace 40,k
41 Replace 41,t
42 Replace 42,k
43 Replace 43,r
44 Replace 44,x
45 Replace 45,r
46 Replace 46,h
47 Replace 47,d
48 Replace 48,b
49 Replace 49,e
50 Replace 50,s

24
1 Insert 1,m
2 Insert 2,p
3 Insert 4,q
4 Replace 6,d
5 Replace 7,l
6 Replace 8,i
7 Replace 10,w
8 Replace 11,n
9 Replace 12,k
10 Replace 13,w
11 Replace 14,g
12 Replace 15,o
13 Replace 16,u
14 Replace 17,v
15 Replace 18,g
16 Replace 19,r
17 Replace 20,s
18 Replace 21,v
19 Replace 22,y
20 Replace 23,l
21 Replace 24,h
22 Replace 25,h
23 Replace 26,z
24 Replace 27,n

38
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Replace 1,u
6 Replace 2,s
7 Delete 4
8 Delete 4
9 Delete 4
10 Delete 4
11 Replace 4,v
12 Delete 6
13 Delete 7
14 Delete 7
15 Delete 7
16 Delete 7
17 Delete 7
18 Delete 7
19 Delete 7
20 Delete 7
21 Delete 8
22 Delete 8
23 Delete 8
24 Delete 8
25 Delete 8
26 Replace 8,i
27 Replace 9,a
28 Replace 10,p
29 Delete 12
30 Replace 12,i
31 Delete 14
32 Delete 14
33 Delete 14
34 Delete 14
35 Delete 14
36 Delete 14
37 Delete 14
38 Delete 14

44
1 Insert 1,k
2 Insert 2,w
3 Replace 3,l
4 Replace 5,h
5 Replace 7,d
6 Replace 8,j
7 Replace 10,a
8 Insert 12,o
9 Replace 14,h
10 Insert 16,r
11 Replace 17,q
12 Replace 18,g
13 Replace 19,o
14 Replace 20,e
15 Replace 21,z
16 Replace 22,t
17 Replace 23,x
18 Insert 25,k
19 Replace 26,g
20 Replace 27,d
21 Replace 28,k
22 Replace 29,h
23 Replace 30,q
24 Replace 31,c
25 Replace 32,d
26 Replace 33,s
27 Replace 34,w
28 Replace 35,r
29 Replace 36,b
30 Insert 38,z
31 Insert 41,i
32 Insert 42,o
33 Insert 43,p
34 Insert 44,j
35 Insert 45,w
36 Replace 46,h
37 Replace 47,e
38 Replace 48,a
39 Replace 49,a
40 Replace 50,j
41 Insert 52,f
42 Insert 53,p
43 Insert 54,a
44 Insert 55,f

48
1 Insert 1,q
2 Insert 2,e
3 Insert 3,p
4 Insert 4,r
5 Insert 5,y
6 Insert 6,q
7 Replace 7,a
8 Replace 8,i
9 Replace 9,w
10 Replace 10,d
11 Replace 11,c
12 Replace 12,r
13 Replace 13,s
14 Replace 14,o
15 Replace 15,m
16 Replace 16,a
17 Insert 19,t
18 Insert 20,f
19 Insert 21,b
20 Insert 22,e
21 Insert 23,e
22 Insert 24,m
23 Replace 26,o
24 Replace 27,p
25 Insert 29,o
26 Insert 30,h
27 Insert 31,y
28 Insert 32,s
29 Replace 33,k
30 Replace 34,f
31 Insert 36,w
32 Insert 37,q
33 Replace 38,i
34 Replace 39,b
35 Replace 40,n
36 Replace 41,h
37 Insert 43,q
38 Insert 45,m
39 Replace 46,x
40 Replace 47,h
41 Replace 48,u
42 Replace 49,p
43 Insert 51,h
44 Replace 52,u
45 Replace 53,q
46 Replace 54,t
47 Replace 56,c
48 Replace 57,x

14
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Delete 1
6 Replace 1,a
7 Replace 3,e
8 Replace 4,x
9 Replace 5,l
10 Replace 6,v
11 Replace 7,d
12 Replace 8,a
13 Replace 9,v
14 Replace 10,q

36
1 Delete 1
2 Replace 1,b
3 Replace 2,w
4 Replace 3,y
5 Replace 4,u
6 Replace 5,e
7 Replace 6,j
8 Replace 7,k
9 Replace 8,w
10 Replace 9,i
11 Replace 10,e
12 Replace 11,s
13 Replace 12,f
14 Replace 13,b
15 Delete 15
16 Delete 15
17 Delete 15
18 Replace 15,d
19 Replace 16,a
20 Replace 17,n
21 Replace 18,j
22 Replace 19,m
23 Delete 21
24 Delete 21
25 Replace 22,d
26 Replace 23,c
27 Replace 25,m
28 Insert 27,x
29 Insert 29,u
30 Insert 30,f
31 Insert 31,t
32 Replace 33,y
33 Replace 34,a
34 Replace 35,b
35 Replace 36,n
36 Replace 37,b

41
1 Replace 1,m
2 Replace 2,i
3 Replace 3,y
4 Replace 4,f
5 Replace 5,a
6 Replace 6,r
7 Replace 7,v
8 Replace 8,o
9 Replace 9,s
10 Replace 10,p
11 Replace 12,e
12 Replace 13,u
13 Replace 14,z
14 Replace 15,i
15 Replace 16,h
16 Replace 17,t
17 Insert 20,q
18 Insert 21,m
19 Insert 22,w
20 Replace 23,w
21 Replace 24,r
22 Replace 25,n
23 Replace 27,e
24 Replace 28,w
25 Replace 29,e
26 Replace 30,h
27 Replace 32,a
28 Replace 33,k
29 Replace 34,x
30 Replace 35,q
31 Replace 36,z
32 Replace 37,g
33 Replace 38,k
34 Replace 39,b
35 Replace 40,r
36 Replace 41,g
37 Replace 42,u
38 Replace 43,r
39 Replace 44,v
40 Replace 45,t
41 Replace 46,w

32
1 Delete 1
2 Delete 1
3 Delete 1
4 Replace 1,z
5 Replace 2,q
6 Replace 3,z
7 Replace 4,s
8 Replace 5,a
9 Replace 6,p
10 Replace 7,u
11 Replace 8,f
12 Replace 9,p
13 Replace 11,q
14 Replace 12,u
15 Replace 13,e
16 Replace 14,d
17 Replace 15,d
18 Delete 17
19 Replace 17,h
20 Replace 18,i
21 Delete 20
22 Delete 20
23 Delete 20
24 Delete 20
25 Delete 20
26 Delete 20
27 Delete 20
28 Delete 20
29 Replace 20,h
30 Replace 21,p
31 Replace 22,c
32 Replace 23,j

37
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Delete 1
6 Delete 1
7 Replace 1,i
8 Delete 3
9 Delete 3
10 Delete 3
11 Delete 3
12 Delete 3
13 Delete 4
14 Delete 4
15 Delete 4
16 Delete 4
17 Replace 4,i
18 Replace 5,x
19 Delete 7
20 Delete 7
21 Delete 7
22 Delete 7
23 Delete 7
24 Delete 7
25 Delete 7
26 Delete 7
27 Delete 7
28 Delete 7
29 Delete 8
30 Delete 8
31 Delete 8
32 Delete 8
33 Delete 8
34 Delete 8
35 Replace 8,k
36 Delete 10
37 Replace 10,f

31
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Delete 1
6 Delete 1
7 Delete 1
8 Delete 1
9 Delete 1
10 Delete 1
11 Delete 1
12 Delete 1
13 Delete 1
14 Delete 1
15 Delete 1
16 Delete 1
17 Delete 1
18 Delete 1
19 Delete 1
20 Replace 1,g
21 Replace 2,w
22 Replace 4,q
23 Replace 5,d
24 Replace 6,q
25 Delete 9
26 Delete 9
27 Replace 9,i
28 Replace 10,d
29 Replace 11,t
30 Replace 12,i
31 Replace 13,o

42
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Delete 1
6 Delete 2
7 Delete 2
8 Delete 2
9 Delete 2
10 Delete 2
11 Delete 2
12 Delete 2
13 Delete 2
14 Delete 2
15 Delete 2
16 Delete 2
17 Delete 4
18 Delete 4
19 Delete 4
20 Replace 4,t
21 Delete 6
22 Replace 6,x
23 Delete 8
24 Delete 8
25 Delete 8
26 Delete 8
27 Delete 8
28 Delete 8
29 Delete 8
30 Delete 8
31 Delete 8
32 Replace 8,g
33 Replace 9,z
34 Replace 11,y
35 Replace 12,n
36 Replace 14,d
37 Replace 15,h
38 Replace 17,i
39 Replace 18,r
40 Replace 19,b
41 Replace 20,c
42 Replace 21,b

47
1 Delete 1
2 Delete 1
3 Delete 1
4 Delete 1
5 Delete 1
6 Delete 1
7 Delete 1
8 Delete 1
9 Delete 1
10 Delete 1
11 Delete 1
12 Delete 1
13 Delete 1
14 Delete 1
15 Replace 1,c
16 Delete 4
17 Delete 4
18 Delete 4
19 Delete 4
20 Delete 4
21 Delete 4
22 Delete 4
23 Delete 4
24 Delete 4
25 Delete 4
26 Delete 5
27 Delete 5
28 Delete 5
29 Delete 5
30 Delete 5
31 Delete 5
32 Delete 5
33 Delete 5
34 Delete 5
35 Delete 5
36 Delete 5
37 Delete 5
38 Delete 5
39 Delete 5
40 Delete 6
41 Delete 6
42 Delete 6
43 Replace 6,g
44 Delete 8
45 Replace 8,t
46 Delete 10
47 Replace 10,y

42
1 Delete 1
2 Delete 1
3 Replace 1,g
4 Delete 3
5 Delete 3
6 Delete 3
7 Delete 3
8 Delete 3
9 Delete 3
10 Delete 3
11 Delete 3
12 Delete 3
13 Delete 3
14 Delete 3
15 Delete 3
16 Delete 3
17 Replace 3,t
18 Replace 4,i
19 Replace 5,g
20 Replace 6,e
21 Replace 7,q
22 Delete 9
23 Replace 9,q
24 Replace 10,l
25 Delete 12
26 Delete 12
27 Delete 12
28 Delete 12
29 Delete 12
30 Delete 12
31 Delete 12
32 Delete 12
33 Delete 13
34 Delete 13
35 Delete 13
36 Delete 13
37 Delete 13
38 Replace 13,k
39 Delete 15
40 Delete 15
41 Delete 15
42 Delete 15

27
1 Insert 1,r
2 Replace 2,u
3 Replace 3,i
4 Replace 4,f
5 Replace 6,j
6 Replace 7,a
7 Replace 8,m
8 Replace 9,m
9 Replace 10,r
10 Replace 11,a
11 Replace 12,y
12 Replace 13,u
13 Insert 15,q
14 Insert 16,i
15 Insert 18,y
16 Insert 19,h
17 Insert 20,m
18 Replace 21,l
19 Replace 22,u
20 Insert 24,k
21 Insert 25,x
22 Insert 26,u
23 Replace 27,x
24 Replace 28,y
25 Replace 30,b
26 Delete 32
27 Replace 32,x