#P4566. [Haoi2016]找相同字符

    ID: 2028 传统题 1000ms 256MiB 尝试: 1588 已通过: 712 难度: 7 上传者: 标签>CF2300提高+/省选-后缀自动机endpos 等价类按长度传播出现次数计数排序贡献法

[Haoi2016]找相同字符

题目描述

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。

两个方案不同当且仅当这两个子串中有一个位置不同。

输入格式

两行,两个字符串 s1,s2s_1,s_2,长度分别为 n1,n2n_1,n_2。

输出格式

输出一个整数表示答案

aabb
bbaa
10

数据规模与约定

对于 100%100\% 的数据,1≤n1,n2≤2×1051 \leq n_1,n_2 \leq 2 \times 10^5,字符串中只有小写字母。