{"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'$ 个字符组成的字符串为 $s''$。他所造出的这个词就是 $s''$。\n\n例如，如果「模板串」为 $s=\\texttt{cciaohalloo}$，那么一种造词方法是，选择 $l=5$，$r=7$，得到 $s'=\\texttt{ccialloo}$，然后选择 $l'=2$，$r'=7$，得到 $s''=\\texttt{ciallo}$。\n\n现在小 δ 有一个「目标串」 $t$，他想知道有多少种不同的方案，可以使用「模板串」$s$ 造出单词 $t$。定义两种方案相同当且仅当选择的 $l,r,l',r'$ 均相同。\n\n## Input\n\n共两行，分别为字符串 $s$ 和 $t$。\n\n## Output\n\n共一行，代表造出「目标串」$t$ 的方案数。\n\n[samples]\n\n## Background\n\n柚子厨差不多得了。\n\n~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/0nqiwonz.png)\n\n## Note\n\n### 数据范围\n\n**本题采用捆绑测试**。\n\n- Subtask 0（6 points）：$|s| \\le 400$，$|t| \\le 200$。\n- Subtask 1（10 points）：$|s| \\le 700$，$|t| \\le 300$。\n- Subtask 2（10 points）：$\\forall i,j,s_i=t_j$。\n- Subtask 3（10 points）：$|t|=1$。\n- Subtask 4（20 points）：$|s| \\le 10^4$，$|t| \\le 3 \\times 10^3$。\n- Subtask 5（14 points）：$|t|=2$。\n- Subtask 6（30 points）：无特殊限制。\n\n对于所有测试数据，$1 \\le |s| \\le 4 \\times 10^5$，$1 \\le |t| \\le 2 \\times 10^5$。$s,t$ 只包含小写英文字母。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9576","tags":["二分","树状数组","洛谷原创","O2优化","哈希 hashing","洛谷月赛"],"sample_group":[["aabbaaba\naba","23"],["ciaohallo\nciallo","2"],["babacbbaababbacbababbabbbaaabaabababbabbabababba\nababab","1535"],["sssssssssssssssssssssssssssssssssssss\nsss","15470"],["abcbbbcbcbcbacbacbaaabcbcbcbaabacbca\ncb","3995"]],"created_at":"2026-03-03 11:09:25"}}