Substrings and reconstruction

Questions 1 to 5 of 8

1. 1. This version of the rolling-row program has no else branch. What does it print? ``cpp #include <algorithm> #include <iostream> #include <string> #include <utility> #include <vector> int main() { const std::string a = "abba"; const std::string b = "aa"; std::vector<int> prev(b.size() + 1, 0), cur(b.size() + 1, 0); int best = 0; for (std::size_t i = 1; i <= a.size(); ++i) { for (std::size_t j = 1; j <= b.size(); ++j) { if (a[i - 1] == b[j - 1]) { cur[j] = prev[j - 1] + 1; best = std::max(best, cur[j]); } } std::swap(prev, cur); } std::cout << best << '\n'; } ``

   1204
2. 2. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <vector> int main() { const std::vector<std::vector<int>> grid = {{1, 3}, {2, 1}}; std::vector<std::vector<int>> best(2, std::vector<int>(2, 0)); for (int r = 0; r < 2; ++r) { for (int c = 0; c < 2; ++c) { if (r == 0 && c == 0) { best[r][c] = grid[r][c]; } else if (r == 0) { best[r][c] = grid[r][c] + best[r][c - 1]; } else if (c == 0) { best[r][c] = grid[r][c] + best[r - 1][c]; } else { best[r][c] = grid[r][c] + std::max(best[r - 1][c], best[r][c - 1]); } } } std::cout << best[1][1] << '\n'; } ``

   4756
3. 3. Which string is the longest common substring of abcd and bcda?

   bcdabccdabcda
4. 4. In the grid program, what does from[r][c] = 'D' mean?

   The robot stops at (r, c)The best path to (r, c) came from the cell to the leftThe value at (r, c) is larger than the value below itThe best path to (r, c) came from the cell above
5. 5. In the rolling-row code, a matching letter sets the cell like this: cur[j] = prev[j - ___] + 1;. What goes in the blank?

   Type your answer.