循环位移
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 1 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
定义字符串 $ S=S_0+\dots+S_{n-1} $ 循环位移 $ k $ 次为 $ S(k) = S_{k\mod n}+\dots + S_{n-1} + S_0 + \dots + S_{(k-1) \mod n} $。
定义 $ [A] = \set{A(k), k \in \mathbb N}. $
给出 $ T $ 组串 $ A, B $，询问 $B$ 有多少个子串在 $ [A] $ 中。
定义 $ [A] = \set{A(k), k \in \mathbb N}. $
给出 $ T $ 组串 $ A, B $，询问 $B$ 有多少个子串在 $ [A] $ 中。
Input
第一行一个 $T$ 表示输入组数。
接下来每行两个字符串，表示 $A$ 和 $B$，保证 $|A| \leq |B|$。
保证 $\sum |B| \leq 1048576.$，并且字符串均由大写字母组成。
接下来每行两个字符串，表示 $A$ 和 $B$，保证 $|A| \leq |B|$。
保证 $\sum |B| \leq 1048576.$，并且字符串均由大写字母组成。
Output
输出 $T$ 行，每行一个数表示答案。
Sample Input
3 AN MANTLEFAN MVP XPTIJMVPMVP CJMR JDRCJMRAJMRCJMGC
Sample Output
2 4 5
Hint
第一个样例：M`AN`TLEFAN,MANTLEF`AN`第三个样例：JD`RCJM`RAJMRCJMGC,JDR`CJMR`AJMRCJMGC,JDRCJMRA`JMRC`JMGC,JDRCJMRAJ`MRCJ`MGC,JDRCJMRAJM`RCJM`GC
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）