Show More
@@ -103,14 +103,14 b' static int equatelines(struct line *a, i' | |||
|
103 | 103 | |
|
104 | 104 | /* clear the hash table */ |
|
105 | 105 | for (i = 0; i <= buckets; i++) { |
|
106 |
h[i].pos = |
|
|
106 | h[i].pos = -1; | |
|
107 | 107 | h[i].len = 0; |
|
108 | 108 | } |
|
109 | 109 | |
|
110 | 110 | /* add lines to the hash table chains */ |
|
111 |
for (i = |
|
|
111 | for (i = 0; i < bn; i++) { | |
|
112 | 112 | /* find the equivalence class */ |
|
113 |
for (j = b[i].hash & buckets; h[j].pos != |
|
|
113 | for (j = b[i].hash & buckets; h[j].pos != -1; | |
|
114 | 114 | j = (j + 1) & buckets) |
|
115 | 115 | if (!cmp(b + i, b + h[j].pos)) |
|
116 | 116 | break; |
@@ -128,7 +128,7 b' static int equatelines(struct line *a, i' | |||
|
128 | 128 | /* match items in a to their equivalence class in b */ |
|
129 | 129 | for (i = 0; i < an; i++) { |
|
130 | 130 | /* find the equivalence class */ |
|
131 |
for (j = a[i].hash & buckets; h[j].pos != |
|
|
131 | for (j = a[i].hash & buckets; h[j].pos != -1; | |
|
132 | 132 | j = (j + 1) & buckets) |
|
133 | 133 | if (!cmp(a + i, b + h[j].pos)) |
|
134 | 134 | break; |
@@ -137,7 +137,7 b' static int equatelines(struct line *a, i' | |||
|
137 | 137 | if (h[j].len <= t) |
|
138 | 138 | a[i].n = h[j].pos; /* point to head of match list */ |
|
139 | 139 | else |
|
140 |
a[i].n = |
|
|
140 | a[i].n = -1; /* too popular */ | |
|
141 | 141 | } |
|
142 | 142 | |
|
143 | 143 | /* discard hash tables */ |
@@ -151,12 +151,12 b' static int longest_match(struct line *a,' | |||
|
151 | 151 | int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k; |
|
152 | 152 | |
|
153 | 153 | for (i = a1; i < a2; i++) { |
|
154 |
/* skip |
|
|
155 |
for (j = a[i].n; j |
|
|
154 | /* skip all lines in b after the current block */ | |
|
155 | for (j = a[i].n; j >= b2; j = b[j].n) | |
|
156 | 156 | ; |
|
157 | 157 | |
|
158 | 158 | /* loop through all lines match a[i] in b */ |
|
159 |
for (; j |
|
|
159 | for (; j >= b1; j = b[j].n) { | |
|
160 | 160 | /* does this extend an earlier match? */ |
|
161 | 161 | if (i > a1 && j > b1 && pos[j - 1].pos == i - 1) |
|
162 | 162 | k = pos[j - 1].len + 1; |
@@ -166,7 +166,7 b' static int longest_match(struct line *a,' | |||
|
166 | 166 | pos[j].len = k; |
|
167 | 167 | |
|
168 | 168 | /* best match so far? */ |
|
169 | if (k > mk) { | |
|
169 | if (k > mk || (k == mk && i <= mi)) { | |
|
170 | 170 | mi = i; |
|
171 | 171 | mj = j; |
|
172 | 172 | mk = k; |
@@ -52,6 +52,9 b' def showdiff(a, b):' | |||
|
52 | 52 | pos += l |
|
53 | 53 | showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\nx\n\nz\n") |
|
54 | 54 | showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n") |
|
55 | # we should pick up abbbc. rather than bc.de as the longest match | |
|
56 | showdiff("a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n", | |
|
57 | "a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n") | |
|
55 | 58 | |
|
56 | 59 | print("done") |
|
57 | 60 |
General Comments 0
You need to be logged in to leave comments.
Login now