A. Arthur's Language

Codeforces

IDCF10162A

Time1000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Arthur is an extremely important person and rarely has the time to talk. To minimize the time spent with words, he developed his own language, which he uses on a daily basis. However, it's very hard to understand whatever comes out of his mouth. In order to improve his interaction with the rest of the world, Arthur has asked the Narratives Industrial Complex (CIN in Portuguese) to develop a program which receives a speech S produced by Arthur and a pattern w and prints how many distinct ways we can obtain w by only removing characters from S. Two ways are considered distinct if there is an index 0 ≤ i < |S| such as Si is present in one and not in the other. Since you are considered the most experienced programmer in CIN, your team has trusted you the task of writing this program. The first line consists of a string S(1 ≤ |S| ≤ 105), representing Arthur's speech. S contains only lower and upper case letters. The second and last line consists of a string w(1 ≤ |w| ≤ 10), the pattern to be searched. Print a single integer: The number of distinct ways to obtain w by removing letters from S. Because this number can be large, print the remained of this number divided by 1000000007 = 109 + 7 ## Input The first line consists of a string S(1 ≤ |S| ≤ 105), representing Arthur's speech. S contains only lower and upper case letters.The second and last line consists of a string w(1 ≤ |w| ≤ 10), the pattern to be searched. ## Output Print a single integer: The number of distinct ways to obtain w by removing letters from S. Because this number can be large, print the remained of this number divided by 1000000007 = 109 + 7 [samples]

**Definitions** Let $ S \in \Sigma^* $ be the input string (speech), where $ \Sigma $ is the set of alphanumeric characters. Let $ w \in \Sigma^* $ be the pattern string, with $ |w| \leq 10 $. **Constraints** 1. $ 1 \leq |S| \leq 10^5 $ 2. $ 1 \leq |w| \leq 10 $ 3. All characters in $ S $ and $ w $ are from the set of lowercase and uppercase English letters. **Objective** Compute the number of distinct subsequences of $ S $ that are equal to $ w $, modulo $ 10^9 + 7 $. That is, count the number of strictly increasing sequences of indices $ 0 \leq i_1 < i_2 < \dots < i_{|w|} < |S| $ such that: $$ S[i_1]S[i_2]\dots S[i_{|w|}] = w $$ Let $ dp[j] $ denote the number of ways to match the first $ j $ characters of $ w $ using a prefix of $ S $. We seek $ dp[|w|] \mod (10^9 + 7) $.

API Response (JSON)

{
  "problem": {
    "name": "A. Arthur's Language",
    "description": {
      "content": "Arthur is an extremely important person and rarely has the time to talk. To minimize the time spent with words, he developed his own language, which he uses on a daily basis. However, it's very hard t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10162A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arthur is an extremely important person and rarely has the time to talk. To minimize the time spent with words, he developed his own language, which he uses on a daily basis. However, it's very hard t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S \\in \\Sigma^* $ be the input string (speech), where $ \\Sigma $ is the set of alphanumeric characters.  \nLet $ w \\in \\Sigma^* $ be the pattern string, with $ |w| \\leq 10 $.  \n\n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments