题目描述
给定两个字符串 A,B,长度分别为 n,m。求有多少个有序下标对 (i,j) 满足 1≤i,j≤n,并且将 A 的前 i 个字符与从位置 j 开始的后缀拼接得到的字符串,是 B 的连续子串。
也就是判断字符串 A1A2…AiAjAj+1…An 是否在 B 中出现。对同一个下标对,出现一次或多次都只计一次。
输入格式
第一行一个字符串 A。第二行一个字符串 B。
输出格式
一行一个整数,表示满足条件的下标对数量。
样例
abac
aacabc
3
满足条件的下标对为 (1,3),(1,4),(2,4)。
数据范围
1≤n,m≤5×105,两个字符串都只包含小写英文字母。
| 测试点 |
特殊限制 |
| 1–2 |
n,m≤100 |
| 3–4 |
n,m≤2000 |
| 5–7 |
n,m≤105 |
| 8–10 |
无 |
原 PDF 题面