[CF427D]Match & Catch 题解

本文主要是介绍[CF427D]Match & Catch 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门QAQ

Analysis

半个月来第一次写博客，真的不能懒下去了QAQ

观察到数据范围为 \(n \le 5000\)，显然可以用 \(O(N^2)\) 随便做。

题解里有不少 SAM 的，还看到一个相当简洁的 hash 表做法，但窝比较喜欢 SA，所以参考 SA 那篇题解写了这题。

首先是 SA 比较经典的套路：将两个字符串合在一起，中间用一个字符相连。

然后跑一遍 SA，考虑如何利用 height 数组求出答案。（自己做的时候就卡在这里，最重要的一步qwq）

发现若 \(sa_x\) 和 \(sa_{x-1}\) 的最长公共前缀若只出现了一次，那么必有 \(height_x \gt height_{x-1}\land height_x \gt height_{x+1}\)

显然如果无法满足这个条件，这个前缀就会反复出现。

那么答案就是 \(ans = \min\limits_{x\in [2,n] \land height _{x+1} \lt height_x \gt height_{x-1}} (max(height_{x-1},height_{x+1}) + 1)\)

别忘了枚举 \(x\) 的时候判断 \(sa_x\) 和 \(sa_{x-1}\) 是否属于同一个子串即可QAQ。

时间复杂度 \(O(N\log N)\)。

CODE

Link

这篇关于[CF427D]Match & Catch 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！