本文主要是介绍(FJWC2020) DTOJ 4686. 字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
你喜欢字符串。有人送了你一个仅含小写字母的字符串。
由于你是一名优秀的 OIer，所以你决定对这个字符串展开研究。
定义两个字符串是相似的，当且仅当存在至多一个 i i i，使得这两个字符串中只有第 i i i 个字母不同。
你取出了这个字符串中所有长度为 m m m 的子串。你想知道，对于每个长度为 m m m 的子串，有多少个其它长度为 m m m 的子串与它相似。
子任务 1 ( 10 % ) 1(10\%) 1(10%)： 1 ≤ n ≤ 500 1 \leq n \leq 500 1≤n≤500；
子任务 2 ( 20 % ) 2(20\%) 2(20%)： 1 ≤ n ≤ 5000 1 \leq n \leq 5000 1≤n≤5000；
子任务 3 ( 30 % ) 3(30\%) 3(30%)： 1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 100 1 \leq n \leq 10^5,1\leq m \leq 100 1≤n≤105,1≤m≤100。
子任务 4 ( 40 % ) 4(40\%) 4(40%)：无特殊限制。
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ n 1 \leq n \leq 10^5,1\leq m \leq n 1≤n≤105,1≤m≤n。
题解
考虑转化两个子串相似的条件： l c p lcp lcp和 l c s lcs lcs的长度和不小于 m − 1 m-1 m−1，这样就可将条件转化为前缀和后缀的限制，方便处理。
于是对正、反串各建一个 S A M （ A , B ） SAM（A,B） SAM（A,B），条件就转化为两串前缀在 A A A上的 m x + mx+ mx+两串后缀在 B B B上的 m x mx mx不超过 m − 1 m-1 m−1。
考虑在 A A A上枚举 l c a lca lca，计算子树内每一个点的贡献，发现一个点对后面的贡献是单点修改，区间查询，树状数组维护即可；但这样会漏掉后面对前面的贡献，再用一个树状数组维护区间加，单点查询。计算过程用dsu on tree的思想，轻子树可以随便常数次遍历，重子数只能往下递归一次，注意一下哪些操作需要 l c a lca lca的信息，什么时候需要清空即可，效率 O ( n l o g 2 n ) O(nlog^{2}n) O(nlog2n)。
这篇关于(FJWC2020) DTOJ 4686. 字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
