zcmimi's blog

categories/算法/字符串/共3篇文章

avatar
zcmimi
2020-09-02 07:35:00
avatar
zcmimi
2020-07-22 19:57:00

普通的单模式串匹配

给定模式串A(|A|=m)、文本串B(|B|=n),需要求出所有位置p,满足B串从第p个字符开始的连续m个字符,与A串完全相同

定义匹配函数C(x,y)=[A(x)-B(y)]^2,若A的第x个字符与B的第y个字符匹配

avatar
zcmimi
2020-05-13 19:00:00

简介

后缀数组,又称SA

是OI中处理字符串的有力工具

实现

有两种实现的方法

  1. 倍增法
  2. DC3

这里主要讲倍增法

sa[i]表示所有后缀中的字典序排名为i的后缀的起始位置

rnk[i]表示起始位置为i的后缀(后缀i)在所有后缀中的排名

1/1
Search
search