12.10 Suppose that in the linear-time suffix array construction algorithm, instead of constructing three groups, we construct seven groups, using for k = 0, 1, 2, 3, 4, 5, 6 Sk = < S[7i + k]S[7i + k + 1]S[7i + k + 2] . . . S[7i + k + 6] for i = 0, 1, 2, . . . > a. Show that with a recursive call to S3S5S6, we have enough information to sort the other four groups S0, S1, S2, and S4. b. Show that this partitioning leads to a linear-time algorithm. - | |
| View Solution | |
| << Back | Next >> |