后缀数组(后续)

    科技2025-05-23  38

    文章目录

    **后缀数组 Height** 两个子串最长公共前缀 **求Height数组** 比较一个字符串的两个子串的大小关系 不同子串的数目 出现至少k次的子串的最大长度 **总结:** 代码:

    后缀数组 Height

    利用后缀数组快速求出2个后缀的lcp长度 lcp:最长公共前缀 lcp(suf(i),suf(j)) 记Height[l] = 排名第(l-1)后缀和排名第l后缀的lcp长度 Height[l] = lcp(suf(SA[l-1]),suf(SA[l]))

    l = 后缀suf(i)的排名 r = 后缀suf(j)的排名 结论:

    两个子串最长公共前缀

    lcp(suf(i),suf(j)) = min(Height[l+1]…Height[r] ) 即两个后缀的lcp = 它们排名区间中Height的最小值 维护rmq

    求Height数组

    Processed: 0.010, SQL: 8