[CF427D]Match & Catch(后缀数组)

题目链接

题解

题目大意:求最小不重复相同子串。

考虑把两个字符串合并起来,求出sa,rk和Height数组。

我们可以从小到大枚举子串长度k,然后再枚举后缀。
具体来说,我们是根据子串字典序从小到大枚举后缀的
如果Height[i]不小于k(即第i-1个子串和第i个子串的最长公共前缀不小于k),
并且如果此后缀的起始点在第一个字符串,cnt1++
否则cnt2++

cnt1和cnt2分别代表最长公共子串出现在第一个字符串和第二个字符串的次数,由于是连续更新的,所以假如上一轮cnt1=1,现在更新cnt2=1那么说明这两个子符串有相同的长度大于k的公共子串,但是不是唯一还不知道。
也就是说这个数字只在两轮更新中有用,如果cnt1>1或cnt2>1都没有价值了(要么没有公共子串,要么有重复的)。
如果要确保唯一性,就要当Height[i]枚举到小于k的时候,如果此时cnt1==1&&cnt2==1的话,则有解。

代码

点赞

发表评论

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