匹配统计

Luogu

IDLGP10479

Time1000ms

Memory512MB

DifficultyP3

O2优化哈希 hashing

阿轩在纸上写了两个字符串，分别记为 $A$ 和 $B$。利用在数据结构与算法课上学到的知识，他很容易地求出了"字符串 $A$ 从任意位置开始的后缀子串“与“字符串 $B$”匹配的长度。不过阿轩是一个勤学好问的同学，他向你提出了 $Q$ 个问题：在每个问题中，他给定你一个整数 $X$，请你告诉他有多少个位置，满足“字符串 $A$ 从该位置开始的后缀子串"与 $B$ 匹配的长度恰好为 $X$。例如：A=aabcde，B=ab，则 $A$ 有 aabcde、abcde、bcde、cde、de、e 这 $6$ 个后缀子串，它们与 $B=ab$ 的匹配长度分别是 $1,2,0,0,0,0$。因此 $A$ 有 $4$ 个位置与 $B$ 的匹配长度恰好为 $0$，有 $1$ 个位置的匹配长度恰好为 $1$，有 $1$ 个位置的匹配长度恰好为 $2$。 ## Input 第一行三个整数 $N,M,Q$，表示 $A$ 串长度、$B$ 串长度、问题个数。第二行是字符串 $A$，第三行是字符串 $B$。接下来 $Q$ 行每行 $1$ 个整数 $x$，表示一个问题。 ## Output 共 $Q$ 行，依次表示每个问题的答案。 [samples] ## Note 数据保证，$1\leq N,M,Q,X\leq 200000$。

Samples

Input #1

6 2 5
aabcde
ab
0
1
2
3
4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "匹配统计",
    "description": {
      "content": "阿轩在纸上写了两个字符串，分别记为 $A$ 和 $B$。利用在数据结构与算法课上学到的知识，他很容易地求出了\"字符串 $A$ 从任意位置开始的后缀子串“与“字符串 $B$”匹配的长度。 不过阿轩是一个勤学好问的同学，他向你提出了 $Q$ 个问题：在每个问题中，他给定你一个整数 $X$，请你告诉他有多少个位置，满足“字符串 $A$ 从该位置开始的后缀子串\"与 $B$ 匹配的长度恰好为 $X$。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10479"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "阿轩在纸上写了两个字符串，分别记为 $A$ 和 $B$。利用在数据结构与算法课上学到的知识，他很容易地求出了\"字符串 $A$ 从任意位置开始的后缀子串“与“字符串 $B$”匹配的长度。\n\n不过阿轩是一个勤学好问的同学，他向你提出了 $Q$ 个问题：在每个问题中，他给定你一个整数 $X$，请你告诉他有多少个位置，满足“字符串 $A$ 从该位置开始的后缀子串\"与 $B$ 匹配的长度恰好为 $X$。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments