[语言月赛 202407] respect

Luogu
IDLGB4014
Time1000ms
Memory512MB
DifficultyP2
2024字符串(入门)语言月赛
小 A 认为,当一个人被尊重时,他便是有尊严的。 现在小 A 对小 B 说了 $n$ 句话,每句话可以被视作为不含空格且全是小写字母的字符串。 每句话是由若干个单词构成的。虽然我们把这些单词直接拼接成了字符串,但是句子的语义还是和单词本身相关。对于一个字符串 $s$,我们会给出一个划分序列 $p_1, p_2, \dots, p_k$,满足 $1 \leq p_1 \leq p_2 \leq \dots \leq p_k <|s|$,则我们认为 $s$ 这句话中,$[1, p_1], [p_1+1,p_2], [p_2+1,p_3],\dots [p_k + 1, |s|]$ 这 $k+1$ 段每一段都是一个单词。特别的,如果 $k=0$,说明这个句子本身就是一个单词。 例如,对字符串 $\texttt{irespectyou}$,如果给出的序列 $p$ 为 $1,8$ 则这个字符串有 $\texttt{i}$,$\texttt{respect}$,$\texttt{you}$ 三个单词;如果序列 $p$ 为 $2, 5,7$,则这个字符串有 $\texttt{ir}$,$\texttt{esp}$,$\texttt{ec}$,$\texttt{tyou}$ 四个单词构成。 对于一个字符串 $x$,我们称一个字符串 $y$ 是 $x$ 的子串,当且仅当将 $x$ 在开头和结尾删去若干个(可以为 $0$ 个)字符后得到的字符串和 $y$ 相等。例如 $\texttt{uog}$ 是 $\texttt{luogu}$ 的子串,但 $\texttt{ug}$ 不是 $\texttt{luogu}$ 的子串。 现在,给出这 $n$ 句话,对于每句话,你要求出这句话里有多少个单词含有子串 $\texttt{respect}$。 ## Input 第一行是一个整数 $n$,表示句子的数量。 接下来 $3n$ 行,每三行一组,表示小 A 对小 B 说的一句话: - 每组第一行是一个字符串 $s$ 表示这句话。 - 第二行是一个整数 $k$ 表示划分序列的长度。 - 第三行是 $k$ 个整数 $p_1, p_2, \dots, p_k$ 表示划分序列。 注意,如果 $k=0$,输入仍在每组数据的第三行有一个空行。 ## Output 输出 $n$ 行。 对每个句子,输出一行一个整数表示其含有子串 $\texttt{respect}$ 的单词数量。 [samples] ## Background 从前有个荣光的王国,小 A 是里面的国王,他认为人活着要有尊严,今天他要赐予他的子民以尊严。 ## Note ### 数据规模与约定 - 对于 $30\%$ 的数据,划分出的子串的长度 $\leq 7$。 - 对于 $60\%$ 的数据,不存在一个单词不是 $\texttt{respect}$ 且以 $\texttt{respect}$ 为子串。 - 对于 $100\%$ 的数据,$1 \leq n \leq 10^3$,$1 \leq p_1 \leq p_2 \leq \dots \leq p_k < |s|$,$k \geq 0$,输入字符串仅含有小写英文字母,字符串长度不超过 $10^3$。
Samples
Input #1
2
irespectyou
2
1 8
herespectsyou
2
2 10
Output #1
1
1
Input #2
1
respect
0

Output #2
1
API Response (JSON)
{
  "problem": {
    "name": "[语言月赛 202407] respect",
    "description": {
      "content": "小 A 认为,当一个人被尊重时,他便是有尊严的。 现在小 A 对小 B 说了 $n$ 句话,每句话可以被视作为不含空格且全是小写字母的字符串。 每句话是由若干个单词构成的。虽然我们把这些单词直接拼接成了字符串,但是句子的语义还是和单词本身相关。对于一个字符串 $s$,我们会给出一个划分序列 $p_1, p_2, \\dots, p_k$,满足 $1 \\leq p_1 \\leq p_2 \\leq ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4014"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 A 认为,当一个人被尊重时,他便是有尊严的。\n\n现在小 A 对小 B 说了 $n$ 句话,每句话可以被视作为不含空格且全是小写字母的字符串。\n\n每句话是由若干个单词构成的。虽然我们把这些单词直接拼接成了字符串,但是句子的语义还是和单词本身相关。对于一个字符串 $s$,我们会给出一个划分序列 $p_1, p_2, \\dots, p_k$,满足 $1 \\leq p_1 \\leq p_2 \\leq ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments