fshp971
  • Home

字符串

A collection of 1 post

hihoCoder 1579 : 统计后缀数组相同的字符串个数
ACM

hihoCoder 1579 : 统计后缀数组相同的字符串个数

今年北京网赛出了一道字符串计数论文题hihoCoder 1579,简单来说就是给定一个后缀数组,统计有多少个仅含小写字母的字符串的后缀数组和它一样。 既然有论文,那就来学习一下咯。论文叫Counting suffix arrays and strings,里面有大段大段看不懂的数学证明,我这里就大概说下结论吧。 令$P[]$为一长度为$n$的后缀数组(此时$P[]$是$n$的一个排列)。 令$R[]$表示$P[]$对应的rank数组。$R[i]=j$当且仅当$P[

  • fshp971
    fshp971
2 min read
fshp971 © 2025
Latest Posts Ghost