#P10382. [2021年联测]字符串

    ID: 9500 传统题 3000ms 888MiB 尝试: 17 已通过: 1 难度: 9 上传者: 标签>CF2800字符串后缀数组线段树LCA数据结构字符串哈希模拟

[2021年联测]字符串

题目描述

给定两个字符串 A,BA,B,长度分别为 n,mn,m。求有多少个有序下标对 (i,j)(i,j) 满足 1≤i,j≤n1\le i,j\le n,并且将 AA 的前 ii 个字符与从位置 jj 开始的后缀拼接得到的字符串,是 BB 的连续子串。

也就是判断字符串 A1A2…AiAjAj+1…AnA_1A_2\ldots A_iA_jA_{j+1}\ldots A_n 是否在 BB 中出现。对同一个下标对,出现一次或多次都只计一次。

输入格式

第一行一个字符串 AA。第二行一个字符串 BB。

输出格式

一行一个整数,表示满足条件的下标对数量。

样例

abac
aacabc
3

满足条件的下标对为 (1,3),(1,4),(2,4)(1,3),(1,4),(2,4)。

数据范围

1≤n,m≤5×1051\le n,m\le5\times10^5,两个字符串都只包含小写英文字母。

测试点 特殊限制
1–2 n,m≤100n,m\le100
3–4 n,m≤2000n,m\le2000
5–7 n,m≤105n,m\le10^5
8–10 无

原 PDF 题面