#P18051. Circular Matching
Circular Matching
Circular Matching
给定两个仅含小写英文字母的字符串 。
对于 的子串 ,令其长度为 ,并将该子串首尾相接成一个环。只有 时,才可能认为 出现在该环上。
更准确地说,若存在整数 ,,使得对于每个 ,均有
则称这对 合法。
求合法的下标对 的数量。即使两个子串的内容相同,只要位置不同,也要分别计数。
输入格式
第一行整数 ,。每个用例两行,分别给出 和 。
。一个输入文件内,所有 的和、所有 的和分别不超过 。
输出格式
每个用例输出一行一个整数,表示合法下标对的数量。
样例
输入:
3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa
输出:
3
3
10