YZOJ P3939 [HAOI2016]找相同字符

YZOJ P3939 [HAOI2016]找相同字符

时间限制:1000MS      内存限制:262144K

难度:\(6.5\)

  • 题目描述

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

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

  • 输入格式

两行,两个字符串 \(s_1, s_2\),\(1 \leq \left|s_1\right|, \left|s_2\right|\leq 200000\),字符串中只有小写字母。

  • 输出格式

输出一个整数表示答案

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 4566


 

 

 

广义SAM 或者 在SAM上跑匹配 都能做。

比如建立 广义SAM,处理出每个节点的 \(right_1, right_2\) 集合的大小,然后答案就是 \(\sum\limits_{x}{\left(max_x-min_x+1\right) \times \left|right_1\right| \times \left|right_2\right|}\) 。

跑匹配的话有点复杂。

首先对 \(s_1\) 建立SAM,\(s_2\) 放在上面跑匹配,失配了就通过 parent 跳回去。

注意到若匹配到这一节点时已经匹配的长度为 \(len\) ,那么长度 \(\leq len\) 的字符串(为当前字符串的后缀)也都已经被匹配,即这个节点沿着 parent 树向上的所有节点都被匹配了。

所以按照拓扑序预处理每个节点完全被匹配对答案的贡献 \(ans\),即通过 parent 树关系向下贡献,有 \(ans_x=ans_{parent_x}+\left(max_x-min_x+1\right) \times \left|right\right|\) 。

匹配到节点 \(x\) ,已经匹配的长度为 \(len\),那么其对答案的贡献为 \(ans_{parent_x}+\left(len-min_x+1\right) \times \left|right\right|\) 。

 

 

 

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注