因为不会SAM
看了一下午后缀数组题解
题目链接
题意:
问:字典序第k小的子串是哪个?
t为0则表示不同位置的相同子串算作一个,
t为1则表示不同位置的相同子串算作多个。
解法:
t=0时:
先运行一遍后缀数组
suffix[sa[i]]有n-sa[i]+1-height[i]前缀(本质不同的子串)
减height[i],由height数组定义能想到有height[i]个前缀算在suffix[sa[i]-1]里面
只要像平衡树/权值树类似做法就能求出第k小了
t=1时:
dalao题解看了我好久才脑补出啥意思OxO
这里就标一下变量啥意思(代码里)
不详细说了(口糊能力差QaQ)
代码:
1 |
|