「TAOI-2」Ciallo~(∠・ω< )⌒★

Luogu
IDLGP9576
Time2000ms
Memory512MB
DifficultyP6
二分树状数组洛谷原创O2优化哈希 hashing洛谷月赛
小 δ 喜欢造词。他学习了一种造词方法。 首先,他拥有一个「模板串」,设为 $s$。然后他会选择一对 $1 \le l \le r \le |s|$,将 $s$ 的第 $l$ 至 $r$ 个字符删掉,把两边的字符串拼起来,他设得到的这个新字符串为 $s'$。 接下来,他会选择一对新的 $1 \le l' \le r' \le |s'|$,然后设 $s'$ 的第 $l'$ 至 $r'$ 个字符组成的字符串为 $s''$。他所造出的这个词就是 $s''$。 例如,如果「模板串」为 $s=\texttt{cciaohalloo}$,那么一种造词方法是,选择 $l=5$,$r=7$,得到 $s'=\texttt{ccialloo}$,然后选择 $l'=2$,$r'=7$,得到 $s''=\texttt{ciallo}$。 现在小 δ 有一个「目标串」 $t$,他想知道有多少种不同的方案,可以使用「模板串」$s$ 造出单词 $t$。定义两种方案相同当且仅当选择的 $l,r,l',r'$ 均相同。 ## Input 共两行,分别为字符串 $s$ 和 $t$。 ## Output 共一行,代表造出「目标串」$t$ 的方案数。 [samples] ## Background 柚子厨差不多得了。 ~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<) ![](https://cdn.luogu.com.cn/upload/image_hosting/0nqiwonz.png) ## Note ### 数据范围 **本题采用捆绑测试**。 - Subtask 0(6 points):$|s| \le 400$,$|t| \le 200$。 - Subtask 1(10 points):$|s| \le 700$,$|t| \le 300$。 - Subtask 2(10 points):$\forall i,j,s_i=t_j$。 - Subtask 3(10 points):$|t|=1$。 - Subtask 4(20 points):$|s| \le 10^4$,$|t| \le 3 \times 10^3$。 - Subtask 5(14 points):$|t|=2$。 - Subtask 6(30 points):无特殊限制。 对于所有测试数据,$1 \le |s| \le 4 \times 10^5$,$1 \le |t| \le 2 \times 10^5$。$s,t$ 只包含小写英文字母。
Samples
Input #1
aabbaaba
aba
Output #1
23
Input #2
ciaohallo
ciallo
Output #2
2
Input #3
babacbbaababbacbababbabbbaaabaabababbabbabababba
ababab
Output #3
1535
Input #4
sssssssssssssssssssssssssssssssssssss
sss
Output #4
15470
Input #5
abcbbbcbcbcbacbacbaaabcbcbcbaabacbca
cb
Output #5
3995
API Response (JSON)
{
  "problem": {
    "name": "「TAOI-2」Ciallo~(∠・ω< )⌒★",
    "description": {
      "content": "小 δ 喜欢造词。他学习了一种造词方法。 首先,他拥有一个「模板串」,设为 $s$。然后他会选择一对 $1 \\le l \\le r \\le |s|$,将 $s$ 的第 $l$ 至 $r$ 个字符删掉,把两边的字符串拼起来,他设得到的这个新字符串为 $s'$。 接下来,他会选择一对新的 $1 \\le l' \\le r' \\le |s'|$,然后设 $s'$ 的第 $l'$ 至 $r'$ 个字符组",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9576"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 δ 喜欢造词。他学习了一种造词方法。\n\n首先,他拥有一个「模板串」,设为 $s$。然后他会选择一对 $1 \\le l \\le r \\le |s|$,将 $s$ 的第 $l$ 至 $r$ 个字符删掉,把两边的字符串拼起来,他设得到的这个新字符串为 $s'$。\n\n接下来,他会选择一对新的 $1 \\le l' \\le r' \\le |s'|$,然后设 $s'$ 的第 $l'$ 至 $r'$ 个字符组...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments