Matching and distinct subsequences

Questions 1 to 5 of 8

1. 1. What does this program print? ``cpp #include <cstddef> #include <cstdint> #include <iostream> #include <string_view> #include <vector> std::uint64_t count(std::string_view s, std::string_view t) { std::vector<std::vector<std::uint64_t>> dp(s.size() + 1, std::vector<std::uint64_t>(t.size() + 1, 0)); for (std::size_t i = 0; i <= s.size(); ++i) dp[i][0] = 1; for (std::size_t i = 1; i <= s.size(); ++i) { for (std::size_t j = 1; j <= t.size(); ++j) { dp[i][j] = dp[i - 1][j]; if (s[i - 1] == t[j - 1]) dp[i][j] += dp[i - 1][j - 1]; } } return dp[s.size()][t.size()]; } int main() { std::cout << count("aaaa", "aa") << '\n'; } ``

   46310
2. 2. What does this program print? ``cpp #include <iostream> #include <string_view> #include <vector> int main() { std::string_view p = "x*y*z"; std::vector<bool> row(p.size() + 1, false); row[0] = true; for (std::size_t j = 2; j <= p.size(); ++j) { if (p[j - 1] == '*') row[j] = row[j - 2]; } for (bool b : row) std::cout << (b ? 'T' : '.'); std::cout << '\n'; } ``

   TTTTTTT......T.T.TT.T.T.
3. 3. Assume the empty-text row is filled in correctly. The star branch of a regex matcher is below. It returns false for the text aa against the pattern a*, but the answer is true. What is missing from this branch? ``cpp if (pc == '*') { dp[i][j] = dp[i][j - 2]; // the star takes zero copies } ``

   The empty-text row that sets dp[0][j] from dp[0][j - 2]The check that rejects a star at the start of the patternThe check that the letter matches s[i - 1] and dp[i - 1][j] is true, so the star can take one more copyThe else branch for a plain letter or dot
4. 4. Assume the first column is set to 1, as the lesson says. This version prints 2 for rabbbit and rabbit, but the answer is 3. What is the bug? ``cpp for (std::size_t i = 1; i <= n; ++i) { for (std::size_t j = 1; j <= m; ++j) { dp[i][j] = 0; if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]; } } } ``

   The cell is set to 0 when the letters differ, so the ways that skip the last letter of s (dp[i - 1][j]) are lostThe table should have m + 1 rows instead of n + 1The first column should be 0, not 1The counts should be signed int to avoid overflow
5. 5. The pattern x*y is matched against four texts. Which text does NOT match?

   yxxyxxzxy