src/opt/lev_dis/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | //@return ans[i][j] = lev(a[0..i), b[0..j)) | ||
| 8 | template <common_range T> | ||
| 9 | 50 | CEXP vvecu lev_dis(T CR a, T CR b) NE { | |
| 10 | 50 | cu32 n = (u32)a.size(), m = (u32)b.size(); | |
| 11 | 100 | vvecu ans(n + 1, vecu(m + 1)); | |
| 12 |
2/2✓ Branch 2 taken 11725 times.
✓ Branch 3 taken 50 times.
|
11775 | flt_ (u32, i, 0, n + 1) ans[i][0] = i; |
| 13 |
2/2✓ Branch 2 taken 11071 times.
✓ Branch 3 taken 50 times.
|
11121 | flt_ (u32, i, 0, m + 1) ans[0][i] = i; |
| 14 |
2/2✓ Branch 0 taken 11675 times.
✓ Branch 1 taken 50 times.
|
11725 | flt_ (u32, i, 1, n + 1) |
| 15 |
2/2✓ Branch 11 taken 7388652 times.
✓ Branch 12 taken 11675 times.
|
7400327 | flt_ (u32, j, 1, m + 1) ans[i][j] = min({ans[i - 1][j - 1] + !(a[i - 1] == b[j - 1]), ans[i][j - 1] + 1, ans[i - 1][j] + 1}); |
| 16 | 50 | return ans; | |
| 17 | } | ||
| 18 | |||
| 19 | } // namespace tifa_libs | ||
| 20 |